Mã giả
Bài học 4 trên 9 trong khóa học Sắp xếp tô pô trong đồ thị của Coddy.
topologicalSort(n, edges):
build directed adjacency; compute indeg[v] for all v
order = []
repeat n times:
pick = smallest v with indeg[v] == 0 (none left -> stop)
mark pick as used (indeg[pick] = -1)
order.add(pick)
for nb in adj[pick]:
indeg[nb] -= 1
return order- indeg[v] đếm số cạnh đi vào. Chỉ các cạnh
u -> vmới được tính vàoindeg[v]. - Duyệt các đỉnh từ
0..n-1và chọn đỉnh đầu tiên có bậc vào bằng 0 sẽ cho ta lựa chọn nhỏ nhất ở mỗi bước, vì vậy thứ tự luôn xác định. - Đặt
indeg[pick] = -1là cách đơn giản để đánh dấu một đỉnh đã được xếp.
Tự làm thử
Bài học này không có thử thách code.
Bài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Sắp xếp tô pô trong đồ thị
Tự luyện tập: Trình biên dịch C online