Silnie spójne składowe
Grupowanie wzajemnie osiągalnych wierzchołków za pomocą algorytmu Tarjana
Silnie spójne składowe to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 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.
Czym jest SCC
Silnie spójna składowa to maksymalna grupa wierzchołków, w której z każdego wierzchołka można dotrzeć do każdego innego, podążając skierowanymi krawędziami.
Dlaczego to ważne
Zastąpienie każdej SCC jednym superwierzchołkiem zmienia dowolny graf skierowany w graf DAG. Dzięki temu wzajemne zależności stają się łatwe do przeanalizowania.
Tarjan w jednym przejściu
Algorytm Tarjan's znajduje wszystkie SCC podczas jednego przejścia DFS. Działa w czasie O(V + E), czyli takim samym jak jedno zwykłe przejście.
Numery odwiedzenia
Przypisz każdemu wierzchołkowi czas odwiedzenia zgodnie z kolejnością, w jakiej DFS odwiedza go po raz pierwszy. Te identyfikatory pozwalają porównywać, który wierzchołek odwiedzono wcześniej.
disc = [-1] * n
timer = 0Wartość low-link
Wartość low-link wierzchołka to najmniejszy identyfikator odwiedzenia osiągalny z tego wierzchołka, także za pośrednictwem krawędzi wstecznych. Wyznacza ona granicę składowej.
low = [-1] * nUmieść na stosie
Gdy DFS wchodzi do wierzchołka, ustaw jego disc i low, a następnie umieść go na stosie wierzchołków, które mogą należeć do tej samej składowej.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueAktualizuj low na podstawie dzieci
Po wywołaniu rekurencji dla nieodwiedzonego dziecka przenieś jego wartość low w górę: low[u] staje się minimum swojej dotychczasowej wartości i low dziecka.
dfs(v)
low[u] = min(low[u], low[v])Obsłuż krawędzie wsteczne
Jeśli sąsiad znajduje się już na stosie, jest przodkiem w tej SCC. Użyj jego disc, aby zmniejszyć low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Znajdź korzeń składowej
Gdy low[u] equals disc[u], wierzchołek u jest korzeniem SCC. Wszystkie elementy znajdujące się nad nim na stosie należą do tej samej składowej.
Zdejmij składową ze stosu
Po znalezieniu korzenia zdejmuj wierzchołki ze stosu aż do usunięcia u. Zdjęta grupa jest dokładnie jedną silnie spójną składową.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju jako alternatywa
Wolisz dwa przejścia? Algorytm Kosaraju's wykonuje DFS, odwraca każdą krawędź, a następnie ponownie wykonuje DFS w kolejności zakończenia, aby wydzielić SCC.
Szybkie sprawdzenie
Podczas DFS algorytmu Tarjan's wierzchołek u spełnia warunek low[u] == disc[u]. Co to oznacza?
Podsumowanie: SCC z algorytmem Tarjana
Śledź disc i low podczas jednego DFS, umieszczaj aktywne wierzchołki na stosie i zdejmuj składową, gdy low equals disc. SCC w czasie O(V+E). 🧩
Często zadawane pytania
Czy lekcja „Silnie spójne składowe” jest bezpłatna?
Tak — pełny tekst „Silnie spójne składowe” 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 „Silnie spójne składowe”?
Grupowanie wzajemnie osiągalnych wierzchołków za pomocą algorytmu Tarjana Ć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 3 z 4.
Ile czasu zajmuje lekcja „Silnie spójne składowe”?
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