Sortowanie topologiczne algorytmem Kahna
Porządkowanie zadań zależnych od innych
Sortowanie topologiczne algorytmem Kahna to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Czym jest porządek topologiczny
Porządek topologiczny wymienia wszystkie wierzchołki grafu skierowanego tak, aby każda krawędź prowadziła od wcześniejszego do późniejszego wierzchołka. Można o nim myśleć jak o kolejności zadań poprzedzających zadania, które ich wymagają.
Dozwolone są tylko grafy DAG
To działa tylko dla grafu DAG, czyli skierowanego grafu acyklicznego. Jeśli istnieje cykl, żaden poprawny porządek nie może spełnić wszystkich zależności.
Idea stopnia wejściowego
Algorytm Kahna opiera się na stopniu wejściowym: liczbie krawędzi skierowanych do wierzchołka. Wierzchołek o stopniu wejściowym równym zero nie ma niespełnionych zależności.
Policz każdy stopień wejściowy
Pierwsze przejście: przejdź po wszystkich krawędziach i policz, ile razy każdy wierzchołek jest ich celem. Otrzymasz w ten sposób stopień wejściowy każdego wierzchołka.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Zainicjuj kolejkę gotowych wierzchołków
Każdy wierzchołek o stopniu wejściowym równym zero jest od razu gotowy, więc na początek dodaj je wszystkie do kolejki.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Przetwórz jeden wierzchołek
Pobierz gotowy wierzchołek i dodaj go do porządku. Jest teraz bezpieczny, ponieważ nie ma już niespełnionych zależności.
u = q.popleft()
order.append(u)Udostępnij jego sąsiadów
Dla każdego sąsiada zmniejsz jego stopień wejściowy o jeden. Gdy sąsiad osiągnie wartość zero, staje się gotowy i trafia do kolejki.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Powtarzaj, aż kolejka będzie pusta
Kontynuuj pobieranie wierzchołków i udostępnianie sąsiadów, aż kolejka się opróżni. Porządek rośnie o jeden bezpieczny wierzchołek naraz, aż wszystkie wierzchołki zostaną umieszczone.
Wykryj cykl bez dodatkowego kosztu
Jeśli końcowy porządek zawiera mniej niż n wierzchołków, resztę uwięził cykl. Algorytm Kahna zapewnia wykrywanie cykli bez dodatkowego kosztu.
if len(order) < n:
print('cycle exists')Czas działania
Każdy wierzchołek i każda krawędź są odwiedzane raz, więc algorytm Kahna działa w czasie O(V + E). Dzięki temu skaluje się do grafów z milionami krawędzi.
Wiele poprawnych porządków
Gdy kilka wierzchołków jest jednocześnie gotowych, dowolny z nich może zostać wybrany jako następny. Dlatego graf DAG często ma wiele poprawnych porządków topologicznych, a nie tylko jeden.
Szybkie sprawdzenie
Kończysz algorytm Kahna, ale porządek zawiera mniej niż n wierzchołków. Co to oznacza?
Podsumowanie: algorytm Kahna
Policz stopnie wejściowe, dodaj do kolejki wierzchołki o wartości zero, pobierz wierzchołek, zmniejsz stopnie jego sąsiadów i powtarzaj. To prosty sortowanie topologiczne w czasie O(V+E). 🚀
Często zadawane pytania
Czy lekcja „Sortowanie topologiczne algorytmem Kahna” jest bezpłatna?
Tak — pełny tekst „Sortowanie topologiczne algorytmem Kahna” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Sortowanie topologiczne algorytmem Kahna”?
Porządkowanie zadań zależnych od innych Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Sortowanie topologiczne algorytmem Kahna”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sortowanie topologiczne algorytmem Kahna
- Wykrywanie cykli w grafach skierowanych
- Silnie spójne składowe
- Mosty i punkty artykulacji