Wykrywanie cykli w grafach skierowanych
Kolorowanie wierzchołków w celu znalezienia krawędzi wstecznych
Wykrywanie cykli w grafach skierowanych to bezpłatna lekcja Coding Interview Prep 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep 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. 🔁
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep 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 Coding Interview Prep 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ąć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep 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