Motywacja

Porządek topologiczny istnieje tylko wtedy, gdy graf nie zawiera cykli. Tworzymy go za pomocą algorytmu Kahna, który wielokrotnie usuwa wierzchołek, do którego nie prowadzą już żadne krawędzie.

Dlaczego warto poznać sortowanie topologiczne?

• Porządkowanie z uwzględnieniem ograniczeń: systemy kompilacji, planowanie zadań, wymagania wstępne kursów i przeliczanie arkuszy kalkulacyjnych — wszystkie te zastosowania opierają się na nim.
• Wykrywanie cykli: jeśli nie możesz uporządkować wszystkich wierzchołków, graf musi zawierać cykl.
• Podstawa algorytmów dla DAG-ów: najkrótsze i najdłuższe ścieżki w DAG-u oblicza się w porządku topologicznym.

Może istnieć wiele poprawnych porządków. Aby uzyskać jeden przewidywalny wynik, zawsze usuwamy wierzchołek o najmniejszym numerze, którego stopień wejściowy wynosi 0.