- Bieżący
- Wolne lub odwiedzane
- Umieszczone
- Cykl
Sortowanie topologiczne
Skarpetki przed butami, fundamenty przed ścianami, kurs przed kursem, który go wymaga. Sortowanie topologiczne ustawia wierzchołki grafu z krawędziami jednokierunkowymi w rzędzie, w którym każda krawędź wskazuje do przodu. Wybierz algorytm Kahna albo metodę DFS i idź krok po kroku, aby zobaczyć, jak rośnie kolejność, a potem dodaj cykl, aby zobaczyć, dlaczego wtedy żadna kolejność nie jest możliwa. Naciśnij Odtwórz, aby zobaczyć, jak rośnie kolejność, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Każda krawędź jest jednokierunkowa, jak pokazuje strzałka: czytaj ją jako "to jest przed tamtym". Wybierz metodę: algorytm Kahna najpierw umieszcza wierzchołki bez krawędzi wchodzących, a liczba na każdym wierzchołku mówi, ile krawędzi wchodzących jeszcze mu zostało; metoda DFS stawia każdy wierzchołek na początku, gdy wszystko po nim jest już umieszczone. Rząd pod grafem to dotychczasowa kolejność. Zaznacz Dodaj cykl, aby zobaczyć, jak każda metoda go znajduje. Nowy graf tworzy inny graf; wybierz, ile ma mieć wierzchołków i krawędzi. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Wybierz algorytm Kahna albo metodę DFS.
- Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce.
- Obserwuj, jak pod grafem rośnie kolejność. Zaznacz Dodaj cykl, aby zobaczyć, jak każda metoda go znajduje.
Algorytm Kahna
Policz dla każdego wierzchołka, ile krawędzi do niego wchodzi. Wierzchołek bez nich od niczego nie zależy, więc może być pierwszy. Umieść taki wierzchołek i usuń jego krawędzie wychodzące: wierzchołki, do których prowadziły, mają teraz o jedną krawędź wchodzącą mniej, a niektóre mogą dojść do zera i stać się wolne. Umieszczaj wolne wierzchołki, dopóki jakieś zostały. Jeśli niektóre wierzchołki nigdy nie stały się wolne, czekają na siebie w cyklu i porządek topologiczny nie istnieje.
Metoda DFS
Uruchom przeszukiwanie w głąb z każdego nieodwiedzonego wierzchołka. Wierzchołek jest przetworzony, gdy wszystko, co da się z niego osiągnąć, jest już przetworzone, więc wszystko, co musi być po nim, jest już umieszczone. Stawiaj każdy przetworzony wierzchołek na początku kolejności, a kolejność wyjdzie poprawna. Jeśli przeszukiwanie pójdzie krawędzią do wierzchołka, w którym wciąż jest, ta krawędź zamyka cykl i znów żadna kolejność nie istnieje.
Często zadawane pytania
Czym jest sortowanie topologiczne?
To ustawienie wierzchołków grafu skierowanego w kolejności, w której każda krawędź prowadzi od wcześniejszego wierzchołka do późniejszego. Jeśli krawędzie znaczą "musi być przed", jest to kolejność, w której da się wykonać wszystkie zadania.
Kiedy istnieje porządek topologiczny?
Dokładnie wtedy, gdy graf nie ma cyklu skierowanego, czyli jest skierowanym grafem acyklicznym (DAG). Przy cyklu każdy wierzchołek na nim musiałby być przed samym sobą.
Czy porządek topologiczny jest jednoznaczny?
Zwykle nie. Gdy dwóch wierzchołków nie łączy żaden łańcuch krawędzi, każdy z nich może być pierwszy, więc graf może mieć wiele poprawnych kolejności. Algorytm Kahna i metoda DFS często dają różne.
Jak szybkie jest sortowanie topologiczne?
Obie metody sprawdzają każdy wierzchołek i każdą krawędź stałą liczbę razy, więc praca rośnie jak liczba wierzchołków plus liczba krawędzi.
Czy mój graf jest gdzieś wysyłany?
Nie. Graf powstaje i jest sortowany w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora