Wykrywanie cykli w grafach skierowanych
Kolorowanie wierzchołków w celu znalezienia krawędzi wstecznych
Wykrywanie cykli w grafach skierowanych to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 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.
Dlaczego cykle mają znaczenie
Skierowany cykl oznacza, że zależności tworzą zamkniętą pętlę. Wykrycie cyklu informuje, że nie może istnieć ani porządek topologiczny, ani poprawny harmonogram.
Graf nieskierowany działa inaczej
Wykrywanie cykli w tym przypadku dotyczy kierunku. Podążanie krawędziami w niewłaściwą stronę się nie liczy, więc sztuczki dla grafów nieskierowanych nie mają tu zastosowania.
Idea trzech kolorów
Przypisz każdemu wierzchołkowi jeden z trzech kolorów: biały oznacza nieodwiedzony, szary — przetwarzany, a czarny — w pełni przetworzony.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nSzary oznacza obecność na stosie
Szary wierzchołek znajduje się na bieżącej ścieżce DFS. Został odwiedzony, ale nie zakończono jeszcze przeglądania wszystkich jego potomków.
Wejdź do wierzchołka
Gdy DFS dociera do wierzchołka, przed rozpoczęciem przeglądania oznacz go jako szary. W ten sposób zaznaczasz, że należy do aktywnej ścieżki.
def dfs(u):
color[u] = GRAYSygnał krawędzi wstecznej
Jeśli dotrzesz do sąsiada, który jest już szary, znaleziono krawędź wsteczną prowadzącą do bieżącej ścieżki. Oznacza to cykl.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleWchodź rekurencyjnie do białych
Biały sąsiad jest jeszcze nieodwiedzony, więc wywołaj dla niego rekurencję. Zwróć True natychmiast, gdy którekolwiek głębsze wywołanie zgłosi cykl.
elif color[v] == WHITE and dfs(v):
return TrueCzarny oznacza bezpieczeństwo
Czarny sąsiad został w pełni przeszukany i nie zawiera cyklu, więc można go pominąć. Ponowne odwiedzanie go byłoby tylko stratą czasu.
Zakończ przetwarzanie wierzchołka
Po obsłużeniu wszystkich sąsiadów oznacz wierzchołek jako czarny. Opuszcza on aktywną ścieżkę i zostaje oznaczony jako ukończony.
color[u] = BLACK
return FalsePrzejdź przez każdą składową
Graf może być niespójny, dlatego rozpocznij DFS z każdego wciąż białego wierzchołka, aby sprawdzić cały graf.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Pamiętaj o limicie rekurencji
Głębokie grafy mogą przepełnić stos rekurencji języka Python. Zwiększ limit albo przepisz DFS z użyciem jawnego stosu.
import sys
sys.setrecursionlimit(300000)Szybkie sprawdzenie
Podczas DFS docierasz do sąsiada, który jest obecnie szary. Co właśnie znaleziono?
Podsumowanie: wykrywanie cykli
Koloruj wierzchołki na biało, szaro, a następnie czarno. Szary sąsiad napotkany podczas DFS jest krawędzią wsteczną, co dowodzi istnienia skierowanego cyklu. 🔁
Często zadawane pytania
Czy lekcja „Wykrywanie cykli w grafach skierowanych” jest bezpłatna?
Tak — pełny tekst „Wykrywanie cykli w grafach skierowanych” 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 „Wykrywanie cykli w grafach skierowanych”?
Kolorowanie wierzchołków w celu znalezienia krawędzi wstecznych Ć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 2 z 4.
Ile czasu zajmuje lekcja „Wykrywanie cykli w grafach skierowanych”?
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