Kalkulator Sortowania Topologicznego

O Kalkulator Sortowania Topologicznego

Kalkulator sortowania topologicznego oblicza liniowe uporządkowanie wierzchołków skierowanego grafu acyklicznego (DAG) tak, że każda skierowana krawędź z u do v umieszcza u przed v. Wprowadź swój graf jako listę krawędzi lub listę sąsiedztwa, a narzędzie zwróci porządek topologiczny przy użyciu algorytmu Kahna lub DFS post-order, wykryje cykle (podając dokładną ścieżkę), pogrupuje zadania w warstwy wykonania równoległego, policzy liczbę poprawnych porządków i wyświetli animację każdego kroku na interaktywnym grafie.

Co to jest sortowanie topologiczne?

Dla danego grafu skierowanego G = (V, E), sortowanie topologiczne (lub porządek topologiczny) to liniowe ustawienie v₁, v₂, …, vₙ jego wierzchołków takie, że dla każdej skierowanej krawędzi (u → v), u pojawia się przed v w tym ustawieniu. Porządek topologiczny istnieje wtedy i tylko wtedy, gdy graf nie zawiera cykli skierowanych — czyli gdy jest to DAG. Porządek rzadko jest unikalny: graf może mieć wiele poprawnych sortowań topologicznych, gdy kilka wierzchołków ma jednocześnie stopień wejściowy zero.

Algorytmy używane przez ten kalkulator

Algorytm Kahna (oparty na BFS, 1962)

Algorytm Kahna jest najbardziej intuicyjnym sposobem sortowania topologicznego. W każdym kroku wybiera wierzchołek o stopniu wejściowym zero (brak krawędzi wchodzących), dołącza go do wyniku i "usuwa" z grafu, zmniejszając stopień wejściowy każdego z jego następców. Gdy wiele wierzchołków ma stopień wejściowy zero, rozstrzyganie remisów może wykorzystywać kopiec typu min (dając najmniejszy leksykograficznie porządek) lub kolejkę FIFO (dając kolejność wstawiania). Algorytm Kahna działa w czasie O(|V| + |E|) i służy również jako detektor cykli: jeśli po opróżnieniu kolejki jakikolwiek wierzchołek nadal ma stopień wejściowy > 0, graf zawiera cykl.

DFS post-order (Tarjan, 1976)

Algorytm DFS wykonuje przeszukiwanie w głąb, a gdy wierzchołek kończy działanie (tj. wszyscy jego następcy zostali w pełni zbadani), jest on umieszczany na stosie. Odwrócenie stosu na końcu daje poprawny porządek topologiczny. Wykrywanie cykli jest naturalne: napotkanie wierzchołka, który jest nadal w trakcie przetwarzania (oznaczonego jako SZARY), oznacza znalezienie krawędzi wstecznej, co wyklucza bycie DAG-iem. DFS post-order również działa w czasie O(|V| + |E|).

Warstwy wykonania równoległego

Widok warstwowy DAG-a dzieli jego wierzchołki na poziomy tak, że każda krawędź prowadzi z poziomu o niższym numerze do poziomu o wyższym numerze. Wierzchołki w tej samej warstwie są od siebie niezależne, więc mogą być wykonywane równolegle. Liczba warstw jest równa długości najdłuższej ścieżki plus jeden — jest to ścieżka krytyczna DAG-a, czyli minimalna liczba rund sekwencyjnych potrzebnych do zakończenia wszystkich zadań, nawet przy nieograniczonej równoległości. Ten kalkulator generuje widok warstw automatycznie, gdy danymi wejściowymi jest DAG.

Wykrywanie cykli

Jeśli graf zawiera cykl skierowany, sortowanie topologiczne jest niemożliwe. Nasz kalkulator zgłasza dokładną ścieżkę cyklu (np. A → B → C → A) i zaznacza krawędzie cyklu na czerwono na wizualizacji. Usunięcie dowolnej pojedynczej krawędzi z cyklu wystarcza, aby przywrócić acykliczność.

Formaty wejściowe

Lista krawędzi

Wpisz każdą skierowaną krawędź jako źródło -> cel, oddzielając je przecinkami lub nowymi liniami. Akceptowane warianty strzałek: ->, →, =>, -->, :. Możesz również łączyć krawędzie: A -> B -> C jest skrótem dla A->B i B->C. Etykiety wierzchołków mogą składać się z liter, cyfr, podkreśleń, myślników i kropek.

Lista sąsiedztwa

Wpisz każdy wierzchołek, dwukropek oraz jego bezpośrednich następców (wierzchołki, na które wskazuje). Wierzchołek bez następców również wymaga swojej linii, na przykład D:.

Jak korzystać z tego kalkulatora

1. Wybierz format: Przełączaj między listą krawędzi a listą sąsiedztwa za pomocą przycisków opcji.
2. Wprowadź graf: Wklej swoje dane lub kliknij jeden z szybkich przykładów (kolejność ubierania, wymagania kursów, cele budowania, graf z cyklem i inne).
3. Wybierz algorytm: Kahn leksykograficzny dla unikalnego, powtarzalnego porządku; kolejność wstawiania dla zachowania porządku wejściowego; DFS post-order dla klasycznej metody w głąb; lub Pokaż wszystkie, aby zobaczyć wszystkie porządki obok siebie.
4. Kliknij "Sortuj topologicznie": Poniżej pojawi się porządek, wykrywanie cykli, widok warstw, długość ścieżki krytycznej, całkowita liczba poprawnych porządków oraz interaktywny graf.
5. Eksploruj: Naciśnij Odtwórz, aby obserwować emitowanie każdego wierzchołka krok po kroku. Liczniki stopni wejściowych aktualizują się na żywo. Przeciągnij dowolny węzeł, aby zmienić układ grafu.

Zastosowania w rzeczywistym świecie

Systemy budowania i kompilatory

Narzędzia takie jak make, Bazel, Gradle i npm sortują topologicznie swoje cele budowania, aby każdy cel był kompilowany dopiero po wszystkich jego zależnościach. Cykl w grafie zależności jest zazwyczaj zgłaszany jako błąd krytyczny — system budowania nie może zdecydować, od czego zacząć.

Harmonogramowanie zadań

Menedżerowie projektów używają DAG-ów do reprezentowania zależności zadań. Sortowanie topologiczne daje poprawną kolejność wykonania, a widok warstw określa minimalną liczbę rund przy nieograniczonej równoległości. Najdłuższy łańcuch to ścieżka krytyczna, która określa czas trwania projektu.

Planowanie wymagań wstępnych kursów

Katalog kursów uniwersyteckich to DAG: krawędzie to relacje wymagań wstępnych. Porządek topologiczny to poprawny plan studiów, a warstwy mówią studentom, które zestawy kursów mogą brać równolegle w każdym semestrze.

Przeliczanie arkuszy kalkulacyjnych

Gdy komórka ulega zmianie, arkusz kalkulacyjny musi przeliczyć każdą komórkę podrzędną w kolejności zależności — jest to sortowanie topologiczne DAG-a zależności komórek. Odwołania cykliczne (cykle) są odrzucane przez aplikację.

Menedżery pakietów i ładowarki wtyczek

Apt, pip, Homebrew, Maven i niezliczone systemy wtyczek rozwiązują kolejność instalacji lub ładowania poprzez sortowanie topologiczne swoich DAG-ów zależności.

Rozwiązywanie symboli i harmonogramowanie instrukcji

Kompilatory używają sortowania topologicznego do porządkowania deklaracji, a procesory używają DAG-ów zależności danych do harmonogramowania instrukcji w buforze reorder bez naruszania hazardów danych.

Liczenie porządków topologicznych

Dla DAG-a z n wierzchołkami liczba różnych poprawnych porządków topologicznych może wahać się od 1 (dla całkowicie uporządkowanego łańcucha) do n! (dla grafu bez krawędzi). Obliczenie dokładnej liczby jest ogólnie problemem #P-zupełnym, ale dla grafów do 16 wierzchołków ten kalkulator wylicza je przy użyciu programowania dynamicznego z maską bitową: f(S) = Σ f(S ∪ {v}) po wszystkich v ∉ S, których wszyscy poprzednicy są w S.

Złożoność i wydajność

• Czas: Zarówno algorytm Kahna, jak i DFS post-order działają w czasie O(|V| + |E|) — liniowo względem rozmiaru grafu.
• Miejsce: O(|V|) na śledzenie stopni wejściowych i porządek wyjściowy, plus O(|V| + |E|) na strukturę sąsiedztwa.
• Wykrywanie cykli: Wbudowane w oba algorytmy. Kahn wykrywa cykle, gdy |wynik| < |V|; DFS wykrywa je, gdy napotkana zostanie krawędź wsteczna (SZARY sąsiad).
• Limity w tym narzędziu: do 80 wierzchołków i 800 krawędzi dla interaktywnej wizualizacji. Liczenie porządków jest ograniczone do 16 wierzchołków.

Często zadawane pytania

Co to jest sortowanie topologiczne?

Sortowanie topologiczne skierowanego grafu acyklicznego to liniowe uporządkowanie jego wierzchołków takie, że dla każdej skierowanej krawędzi z u do v, u znajduje się przed v. Reprezentuje ono poprawną kolejność przetwarzania zadań respektującą ich zależności.

Jakiego algorytmu używa ten kalkulator?

Kalkulator uruchamia zarówno algorytm Kahna, jak i DFS post-order. Algorytm Kahna wielokrotnie usuwa wierzchołek o stopniu wejściowym zero i zmniejsza stopnie wejściowe jego następców. DFS post-order wykonuje przeszukiwanie w głąb i odwraca kolejność zakończenia. Oba działają w czasie O(|V| + |E|).

Co jeśli mój graf ma cykl?

Graf z cyklem skierowanym nie posiada sortowania topologicznego. Kalkulator wykrywa cykl, zaznacza go na czerwono na wizualizacji i raportuje dokładną ścieżkę cyklu, abyś wiedział, które krawędzie usunąć, by graf stał się DAG-iem.

Czym jest najmniejszy leksykograficznie porządek topologiczny?

Gdy dostępnych jest wiele poprawnych porządków, najmniejszy leksykograficznie to taki, w którym w każdym kroku wybieramy alfabetycznie najmniejszy wierzchołek o stopniu wejściowym zero. Domyślny tryb Kahna w tym kalkulatorze zwraca ten unikalny, stabilny porządek.

Czym jest widok warstw lub poziomy?

Widok warstw grupuje wierzchołki według najdłuższej ścieżki od źródeł. Wierzchołki w tej samej warstwie nie mają zależności między sobą i mogą być uruchamiane równolegle. Liczba warstw to ścieżka krytyczna projektu.

Czy graf może mieć wiele poprawnych porządków topologicznych?

Tak. Jeśli w dowolnym kroku algorytm Kahna ma kilka wierzchołków ze stopniem wejściowym zero, każdy z nich może być następny. Kalkulator liczy dokładną liczbę takich kombinacji dla grafów do 16 wierzchołków.

Jaka jest różnica między algorytmem Kahna a DFS post-order?

Kahn działa "od góry": wielokrotnie wybiera źródła (stopień 0) i emituje je najpierw. DFS post-order działa "od dołu": najpierw kończy przetwarzanie ujść i dopisuje je na początku wyniku (po odwróceniu). Oba są O(|V| + |E|), ale zazwyczaj dają inne wyniki. Kahn jest łatwiejszy do równoleglenia; DFS łatwiej łączy się z innymi analizami grafowymi.

Jaki jest maksymalny rozmiar grafu obsługiwany przez to narzędzie?

Kalkulator obsługuje do 80 wierzchołków i 800 krawędzi. Liczenie wszystkich porządków jest ograniczone do 16 wierzchołków, ponieważ problem jest #P-zupełny, a przestrzeń stanów rośnie jako 2ⁿ. Animacja i wizualizacja działają płynnie do pełnego limitu rozmiaru.

Dalsza lektura

• Sortowanie topologiczne — Wikipedia (Angielski)
• Skierowany graf acykliczny — Wikipedia
• Przeszukiwanie w głąb — Wikipedia
• Metoda ścieżki krytycznej — Wikipedia
• Silnie spójna składowa — Wikipedia