PL 
EnglishDomyślny
Українська🔀 Sortowanie topologiczne — porządkowanie DAG
Uporządkuj wierzchołki skierowanego grafu acyklicznego tak, by każda krawędź wskazywała do przodu. Zobacz algorytm Kahna zdejmujący węzły o zerowym stopniu wejściowym — to szeregowanie stojące za systemami budowania i wymaganiami wstępnymi kursów.
O tej symulacji
Ta symulacja buduje losowy skierowany graf acykliczny (DAG) — sieć jednokierunkowych połączeń bez pętli — rysując krawędzie wyłącznie od wierzchołka o niższym indeksie do wierzchołka o wyższym indeksie, co matematycznie gwarantuje, że graf początkowy nie ma cyklu. Następnie animuje algorytm Kahna: oblicza stopień wejściowy każdego wierzchołka (liczbę krawędzi wchodzących), umieszcza wszystkie wierzchołki o stopniu wejściowym zero w kolejce, po czym wielokrotnie usuwa jeden z kolejki, dodaje go do rosnącego porządku topologicznego i zmniejsza stopień wejściowy jego następników, dodając do kolejki te, które osiągną zero. Suwak Wierzchołki (4–9) ustawia rozmiar grafu, a suwak Prędkość kontroluje, jak szybko Odtwórz przechodzi przez kolejne kroki.
🔬 Co przedstawia
Każdy wierzchołek wyświetla odznakę „in:” z jego bieżącym stopniem wejściowym. Zielony pierścień oznacza wierzchołek o stopniu wejściowym zero, siedzący w kolejce i gotowy do umieszczenia; pełny fiolet oznacza wierzchołek właśnie usunięty w tym kroku; wyblakły fiolet oznacza wierzchołki już umieszczone; szare wierzchołki wciąż mają niespełnione zależności. Krawędzie blakną, gdy ich wierzchołek źródłowy zostaje usunięty, a rosnący porządek topologiczny pojawia się jako numerowana lista obok płótna.
🎮 Jak korzystać
Przeciągnij suwak Wierzchołki N (4–9), aby zmienić rozmiar grafu, i Wygeneruj ponownie, by narysować nowy losowy DAG. Naciśnij Odtwórz, aby automatycznie uruchomić algorytm Kahna (w tempie ustawionym suwakiem Prędkość) lub Krok, by przejść dokładnie o jedną operację usunięcia-i-zmniejszenia naraz. Dodaj krawędź wstawia jedną dodatkową losową krawędź — zwykle krawędź w przód, która utrzymuje DAG poprawnym, ale czasem krawędź wstecz, tworzącą cykl, którego wykrycie przez symulację można obserwować.
💡 Czy wiesz, że?
Algorytm Kahna opublikował Arthur B. Kahn w 1962 roku w pracy „Topological sorting of large networks” i działa w czasie O(V + E). Rzeczywiste narzędzia budujące, takie jak Make i Bazel, wykorzystują dokładnie tę ideę — traktując pliki lub pakiety jako wierzchołki, a zależności jako krawędzie — aby ustalić bezpieczną kolejność kompilacji i zgłosić twardy błąd w chwili wykrycia cyklu zależności.
Najczęściej zadawane pytania
Jak symulacja gwarantuje, że graf początkowy nie ma cykli?
Każdy wierzchołek otrzymuje stały indeks od 0 do N−1, a kandydujące krawędzie są dodawane wyłącznie od niższego indeksu do wyższego (i do j tylko gdy i < j). Ponieważ krawędź nigdy nie może wskazywać wstecz przy takim indeksowaniu, podążanie za dowolnym łańcuchem krawędzi zawsze zwiększa indeks, więc nie da się wrócić do wierzchołka, od którego się zaczęło — graf jest acykliczny z konstrukcji, jeszcze zanim algorytm Kahna w ogóle się uruchomi.
Co oznaczają kolory wierzchołków i odznaka „in:”?
Odznaka „in:” pokazuje bieżący stopień wejściowy wierzchołka, czyli liczbę krawędzi wciąż do niego wchodzących. Zielony pierścień oznacza stopień wejściowy zero — wierzchołek nie ma niespełnionych zależności i siedzi w kolejce gotowy do umieszczenia. Pełny fiolet oznacza wierzchołek właśnie usunięty w tym kroku, wyblakły fiolet oznacza wierzchołki umieszczone we wcześniejszych krokach, a zwykłe szare wierzchołki wciąż mają co najmniej jedną niespełnioną zależność.
Co się dzieje, gdy kliknę Dodaj krawędź?
Dodaj krawędź wstawia jedną nową losową krawędź i uruchamia algorytm od nowa. W około 60% przypadków wybiera krawędź w przód (z niższego indeksu do wyższego), co utrzymuje graf jako poprawny DAG. W pozostałych przypadkach, lub gdy nie pozostała już żadna krawędź w przód do dodania, wybiera zamiast tego krawędź wstecz, która tworzy cykl, dzięki czemu można zaobserwować reakcję wykrywania cyklu w symulacji.
Jak symulacja wykrywa i zgłasza cykl?
Uruchamia algorytm Kahna do końca, usuwając i umieszczając wierzchołki, aż kolejka się opróżni. Jeśli wszystkie wierzchołki zostały umieszczone, sortowanie się powiodło. Jeśli kolejka opróżni się wcześniej, a wierzchołki pozostają nieumieszczone, te wierzchołki muszą leżeć na cyklu, ponieważ stopień wejściowy cyklu nigdy nie może spaść do zera, a symulacja wypisuje je pod „Cykl wśród” z czerwonym banerem narysowanym na płótnie.
Jaka jest różnica między elementami sterującymi Krok, Odtwórz i Wygeneruj ponownie?
Krok wykonuje dokładnie jedną iterację algorytmu Kahna: usuwa jeden wierzchołek o stopniu wejściowym zero z kolejki, dodaje go do porządku i zmniejsza stopień wejściowy jego następników. Odtwórz powtarza ten sam krok automatycznie, przechodząc mniej więcej co 28 klatek animacji podzielone przez wartość suwaka Prędkość, aż kolejka będzie pusta. Wygeneruj ponownie odrzuca bieżący graf i rysuje zupełnie nowy losowy DAG przy bieżącym ustawieniu Wierzchołki N, resetując stan algorytmu.