Động lực

Thứ tự topo chỉ tồn tại khi đồ thị không có chu trình. Ta tạo thứ tự này bằng thuật toán Kahn, thuật toán liên tục loại bỏ một đỉnh không còn cạnh đi vào.

Tại sao nên học sắp xếp topo?

• Sắp xếp theo các ràng buộc: hệ thống xây dựng, lập lịch tác vụ, điều kiện tiên quyết của khóa học và tính toán lại bảng tính đều dựa vào thuật toán này.
• Phát hiện chu trình: nếu bạn không thể sắp xếp mọi đỉnh, đồ thị phải có chu trình.
• Nền tảng cho các thuật toán DAG: đường đi ngắn nhất và dài nhất trong DAG được tính theo thứ tự topo.

Có thể có nhiều thứ tự hợp lệ. Để luôn có một kết quả nhất quán, ta luôn loại bỏ đỉnh có số nhỏ nhất có bậc vào bằng 0.