Sắp xếp Topo Tier 5 · L32
Sắp xếp tuyến tính đỉnh của DAG sao cho mọi cạnh u → v thì u đứng trước v.
Ba module: Kahn (BFS), DFS post-order, và phát hiện chu trình.
1. Kahn's algorithm — bóc lớp theo in-degree
Đếm in-degree → đỉnh in-degree 0 vào queue → bóc dần, mỗi lần giảm in-degree neighbor → kết xuất topo order. Bấm Bước để chạy từng bước, hoặc Chạy để tự động.
Thử: bóc dần các đỉnh in-degree 0 — nếu chưa hết đỉnh mà không còn đỉnh 0 để bóc → đồ thị có chu trình, không tồn tại thứ tự.
2. DFS post-order — 3 màu, push stack rồi đảo ngược
DFS đi sâu. Đỉnh chuyển gray khi vào đệ quy, black + push stack khi hoàn thành (post-order). Cuối cùng đảo ngược stack ra topo order.
3. Cycle detection — gặp đỉnh gray là back edge
DFS 3 màu. Khi cạnh u → w trỏ tới đỉnh đang gray
(tổ tiên trong stack đệ quy) ⟹ back edge ⟹ chu trình.
Đổi đồ thị để xem trường hợp có và không có chu trình.