Menu
CoddyTech

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 -> v mới được tính vào indeg[v].
  • Duyệt các đỉnh từ 0..n-1 và 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] = -1 là 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.

quiz iconTự kiểm tra

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