giai thuat topo

 Giải thuật Tô pô (Topological Sort) là một giải thuật được sử dụng trong lý thuyết đồ thị để sắp xếp các đỉnh của một đồ thị có hướng (DAG - Directed Acyclic Graph) sao cho đối với mỗi cặp đỉnh u và v, nếu có cạnh từ u đến v thì u đứng trước v trong thứ tự sắp xếp.

Giải thuật Tô pô
Có nhiều cách để thực hiện giải thuật Tô pô, sau đây là một trong những phương pháp phổ biến nhất:

Sử dụng Kahn's Algorithm
Khởi tạo:

Tính bậc vào (in-degree) của mỗi đỉnh trong đồ thị.
Tạo một hàng đợi (queue) lưu trữ các đỉnh có bậc vào bằng 0.
Quá trình:

Khi hàng đợi không rỗng, thực hiện các bước sau:
Lấy đỉnh u ra khỏi hàng đợi.
Đưa đỉnh u vào danh sách kết quả.
Đối với mỗi đỉnh v kề với u (tức là có cạnh từ u đến v), giảm bậc vào của v đi 1.
Nếu bậc vào của v bằng 0, đưa v vào hàng đợi.
Kết thúc:

Nếu tất cả các đỉnh đều được xử lý (có trong danh sách kết quả), thì đồ thị có hướng ban đầu là đồ thị không chu trình (DAG) và danh sách kết quả là thứ tự Tô pô của đồ thị.
Nếu không, đồ thị có chu trình và không có thứ tự Tô pô.
Mã giả của giải thuật Tô pô (Kahn's Algorithm)
plaintext
Sao chép mã
input: Đồ thị có hướng DAG
output: Danh sách thứ tự Tô pô các đỉnh

1. Tính bậc vào của tất cả các đỉnh
2. Tạo một hàng đợi Q chứa tất cả các đỉnh có bậc vào bằng 0
3. Tạo danh sách L rỗng để lưu thứ tự Tô pô

while Q không rỗng do
u = lấy đỉnh đầu tiên từ Q
thêm u vào danh sách L
for mỗi đỉnh v kề với u do
giảm bậc vào của v đi 1
if bậc vào của v bằng 0 then
thêm v vào Q

if tất cả các đỉnh đều có trong L then
return L (thứ tự Tô pô)
else
báo lỗi (đồ thị có chu trình)
Ví dụ minh họa
Giả sử bạn có đồ thị có hướng như sau:

rust
Sao chép mã
5 -> 0 <- 4
| ^
v |
2 -> 3 -> 1
Tính bậc vào:
5: 0, 4: 0, 0: 2, 2: 1, 3: 1, 1: 2
Hàng đợi ban đầu: 5, 4
Thứ tự Tô pô:
Bước 1:

Lấy 5, danh sách L: [5]
Giảm bậc vào của 2: 0, thêm 2 vào hàng đợi
Hàng đợi: 4, 2
Bước 2:

Lấy 4, danh sách L: [5, 4]
Giảm bậc vào của 0: 1
Hàng đợi: 2
Bước 3:

Lấy 2, danh sách L: [5, 4, 2]
Giảm bậc vào của 3: 0, thêm 3 vào hàng đợi
Hàng đợi: 3
Bước 4:

Lấy 3, danh sách L: [5, 4, 2, 3]
Giảm bậc vào của 1: 1, giảm bậc vào của 0: 0, thêm 0 vào hàng đợi
Hàng đợi: 1, 0
Bước 5:

Lấy 1, danh sách L: [5, 4, 2, 3, 1]
Giảm bậc vào không thay đổi
Hàng đợi: 0
Bước 6:

Lấy 0, danh sách L: [5, 4, 2, 3, 1, 0]
Hàng đợi rỗng, kết thúc
Kết quả thứ tự Tô pô: [5, 4, 2, 3, 1, 0]