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ị:

Queue:

Topo order:

Chọn đồ thị rồi bấm "Bước".

chưa xử lý trong queue (in-degree 0) đã vào order

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.

Stack (post-order):

Topo (đảo ngược):

Bấm "Bước" để bắt đầu DFS từ đỉnh 0.

white gray (đang đệ quy) black (xong)

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.

Đồ thị:

Bấm "Bước" để chạy DFS.

white gray black back edge → chu trình