Chuyển tới nội dung chính

Sắp xếp tô-pô (Topological Sort)

Bạn sẽ học được gì

Sắp xếp tô-pô (topological sort) sắp các đỉnh của một DAG (đồ thị có hướng không chu trình) thành một hàng sao cho: nếu có cạnh u -> v thì u đứng trước v. Bạn sẽ học hai cách: Kahn (đếm bậc vào + queue) và DFS. Ứng dụng: xếp lịch học môn tiên quyết, thứ tự biên dịch, lập lịch tác vụ.

1. Trực quan: thứ tự mặc quần áo​

Bạn không thể đi giày trước khi đi tất. Mỗi "việc phải làm trước" là một cạnh có hướng. Sắp xếp tô-pô tìm một trình tự hợp lệ thoả mọi ràng buộc đó.

   tat -> giay
   ao  -> ao khoac
   quan -> giay

   Mot thu tu hop le:  tat, quan, ao, giay, ao khoac
   (moi mui ten u -> v: u luon dung TRUOC v)

Điều kiện bắt buộc: đồ thị không được có chu trình. Nếu A cần B mà B lại cần A thì không thứ tự nào hợp lệ.

2. Cách 1 — Kahn (bậc vào + queue)​

Bậc vào (in-degree) của một đỉnh = số cạnh đi vào nó. Ý tưởng:

BướcHành động
1Tính bậc vào cho mọi đỉnh
2Đẩy mọi đỉnh bậc vào = 0 (không phụ thuộc ai) vào queue
3Lấy một đỉnh ra, thêm vào kết quả; với mỗi cạnh u -> v giảm bậc vào của v
4Nếu bậc vào của v giảm về 0 thì đẩy v vào queue
5Lặp tới khi queue rỗng

Nếu cuối cùng số đỉnh lấy ra nhỏ hơn tổng số đỉnh thì đồ thị có chu trình (không sắp được).

3. Chạy debug: Kahn​

🐞 Kahn trên đồ thị nhỏBước 1/8
1g = {"A": ["C"], "B": ["C"], "C": ["D"], "D": []}
2indeg = {"A":0, "B":0, "C":2, "D":1}
3q = ["A", "B"]; order = []
4while q:
5  u = q.pop(0)
6  order.append(u)
7  for v in g[u]:
8      indeg[v] -= 1
9      if indeg[v] == 0:
10          q.append(v)
Biến tại bước này
q[A,B]
indegC:2 D:1
order[]
👉 A,B có bậc vào 0 → vào queue.

4. Code chạy được​

Cả Kahn (kèm phát hiện chu trình) và DFS.

Đang tải trình chạy code…
Vì sao DFS phải đảo ngược?

Trong DFS, một đỉnh chỉ được ghi vào danh sách sau khi mọi đỉnh nó trỏ tới đã xong. Nên nó nằm ở cuối. Đảo ngược danh sách thì các đỉnh "đứng trước" trở về đúng vị trí đầu.

5. Phân tích​

CáchThời gianBộ nhớĐiểm cộng
KahnO(V + E)O(V)Phát hiện chu trình tự nhiên
DFSO(V + E)O(V)Ngắn gọn, tái dùng DFS

Bẫy thường gặp:

  • Quên kiểm tra chu trình → trả về thứ tự sai cho đồ thị có vòng.
  • Bản DFS quên đảo ngược → ra thứ tự ngược hoàn toàn.

6. Mẫu nhận diện​

  • "Môn tiên quyết", "phải làm A trước B", "phụ thuộc (dependency)" → sắp xếp tô-pô.
  • "Thứ tự biên dịch", "build các module", "lập lịch tác vụ có ràng buộc" → tô-pô.
  • Đồ thị có hướng và bạn cần một trình tự tuyến tính hợp lệ → tô-pô.

7. 🎮 Trò chơi: Hiểu sắp xếp tô-pô​

🎮 Hiểu sắp xếp tô-pôCâu 1/4· Điểm 0· 🔥 0

Tô-pô chỉ áp dụng cho DAG. Nếu u -> v thì u đứng trước v.

Nếu Kahn lấy ra ít đỉnh hơn tổng số đỉnh thì kết luận?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Điều kiện để một đồ thị có thứ tự tô-pô là?
2. Bậc vào (in-degree) của một đỉnh là gì?
3. Độ phức tạp của sắp xếp tô-pô (Kahn hoặc DFS) là?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.3.4 — Dijkstra (đường đi ngắn nhất khi cạnh có trọng số không âm).