Algorytmy i struktury danych · Middle · Pytanie 32 z 75
Jak algorytm Kahna wyznacza porządek topologiczny?
- 1Sortuje wierzchołki po nazwie i sprawdza krawędzie
- ✓Poprawna odpowiedź: Wielokrotnie usuwa wierzchołek bez krawędzi wchodzących
- 3Uruchamia DFS i wypisuje wierzchołki w kolejności pierwszego odwiedzenia
Wyjaśnienie
Trzymamy stopnie wejściowe i kolejkę wierzchołków ze stopniem 0. Jeśli kolejka opustoszeje przed wypisaniem wszystkich wierzchołków, graf ma cykl. Wersja DFS wypisuje wierzchołki w odwrotnej kolejności zakończenia, a nie odwiedzenia.