Sortowanie topologiczne
Za każdym razem, gdy instalujesz oprogramowanie, budujesz program albo planujesz projekt, coś musi ustalić, co zrobić najpierw. Jeśli zadanie B wymaga zadania A, A musi być wcześniej. Sortowanie topologiczne zamienia sieć takich reguł w jedną prostą linię.
Idea
Narysuj każde zadanie jako wierzchołek, a każdą regułę "A przed B" jako strzałkę z A do B. Porządek topologiczny to rząd wszystkich wierzchołków, w którym każda strzałka wskazuje w prawo. Nazywa się to sortowaniem, bo ustawia rzeczy w kolejności, ale w odróżnieniu od sortowania liczb musi tylko szanować strzałki: wierzchołki, których nie łączy żaden łańcuch strzałek, mogą być w dowolnej kolejności.
Kiedy to niemożliwe
Jeśli strzałki tworzą cykl, na przykład A przed B, B przed C i C przed A, to A musiałby być przed samym sobą. Porządek topologiczny istnieje więc dokładnie wtedy, gdy graf nie ma cyklu skierowanego. Taki graf nazywa się skierowanym grafem acyklicznym (DAG). Obie poniższe metody znajdują cykl, jeśli istnieje, więc przydają się też jako test na cykle.
Przykład
Weźmy strzałki A → C, B → C, B → D, C → E i D → E. Algorytm Kahna liczy strzałki wchodzące: A i B nie mają żadnych, więc A idzie pierwszy, potem B. Usunięcie strzałek z B uwalnia C i D, które idą dalej, a potem E: kolejność A, B, C, D, E. Metoda DFS odwiedza A, potem C, potem E; E zostaje przetworzony pierwszy, potem C, potem A, i każdy trafia na początek. Potem odwiedza B i D, które zostają przetworzone przed nimi: kolejność B, D, A, C, E. Obie kolejności są poprawne.
Kahn czy DFS?
Algorytm Kahna, opublikowany przez Arthura Kahna w 1962 roku, działa do przodu: zawsze wie, które zadania można zacząć teraz, co pasuje do planowania, i może wybierać spośród wolnych zadań według dowolnej reguły, na przykład alfabetycznie. Metoda DFS, spopularyzowana przez Roberta Tarjana w 1976 roku, działa wstecz od końców i potrzebuje tylko przeszukiwania w głąb. W obu czas rośnie jak liczba wierzchołków plus krawędzi.
Zastosowania
Narzędzia do budowania, takie jak make, kompilują pliki po plikach, od których one zależą. Menedżery pakietów instalują biblioteki w kolejności zależności. Arkusze kalkulacyjne przeliczają komórkę po komórkach, których używa jej formuła. Uczelnie sprawdzają, czy da się spełnić wymagania wstępne kursów, kompilatory ustalają kolejność instrukcji, a potoki danych uruchamiają każdy krok, gdy jego dane wejściowe są gotowe. Uniksowe polecenie tsort samo wykonuje sortowanie topologiczne.
Wypróbuj
Otwórz aplikację i naciśnij Krok. Strzałki mówią, który wierzchołek musi być przed którym. W algorytmie Kahna liczba na każdym wierzchołku liczy pozostałe strzałki wchodzące, a wolne wierzchołki są niebieskie. W metodzie DFS niebieskie wierzchołki są odwiedzane, a zielone są umieszczone. Kolejność rośnie w rzędzie pod grafem. Zaznacz Dodaj cykl i patrz, jak obie metody odkrywają, że żadna kolejność nie istnieje.
Często zadawane pytania
Co znaczy tu słowo topologiczny?
Nazwa pochodzi od topologii, nauki o tym, jak rzeczy są połączone, a nie o ich dokładnym kształcie. Kolejność zależy tylko od tego, które wierzchołki łączą strzałki, a nie od tego, gdzie są narysowane.
Jak znaleźć cykl, gdy kolejność nie istnieje?
Metoda DFS pokazuje go wprost: krawędź do wierzchołka, który jest wciąż odwiedzany, razem ze ścieżką odwiedzanych wierzchołków tworzy cykl. Algorytm Kahna mówi tylko, które wierzchołki utknęły; przeszukanie wśród nich znajduje cykl.
Czy mogę wybrać konkretną kolejność spośród poprawnych?
Tak. Gdy w algorytmie Kahna kilka wierzchołków jest wolnych, wybierz ten, który wolisz, na przykład z najmniejszą literą albo najpilniejsze zadanie. Kolejka priorytetowa daje kolejność, która jest pierwsza alfabetycznie.
Jak sortowanie topologiczne pomaga w szukaniu najkrótszych ścieżek?
W skierowanym grafie acyklicznym aktualizowanie odległości wzdłuż krawędzi każdego wierzchołka w porządku topologicznym znajduje wszystkie najkrótsze ścieżki od startu w jednym przebiegu, nawet przy ujemnych krawędziach, szybciej niż algorytm Dijkstry czy Bellmana–Forda.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj sortowanie topologiczne