Mosty i punkty artykulacji
Znajdowanie krawędzi i wierzchołków rozspajających graf
Mosty i punkty artykulacji to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 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.
Wrażliwe miejsca w grafie
Niektóre elementy grafu nieskierowanego są krytyczne: ich usunięcie rozspaja graf. Ich znalezienie pozwala odkryć słabe połączenia.
Czym jest most
Most to krawędź, której usunięcie zwiększa liczbę spójnych składowych. Jest jedyną ścieżką łączącą dwa obszary.
Czym jest punkt artykulacji
Punkt artykulacji to wierzchołek, którego usunięcie rozspaja graf. Sieci są szczególnie podatne na takie pojedyncze punkty awarii.
Ponownie o drzewach DFS
Oba algorytmy opierają się na jednym DFS i śledzą czas odwiedzenia oraz wartość low, podobnie jak algorytm Tarjana, ale działają na grafie nieskierowanym.
disc = [-1] * n
low = [-1] * nLow oznacza najwcześniejsze osiągnięcie
Low wierzchołka to najwcześniejszy identyfikator odwiedzenia osiągalny z jego poddrzewa DFS, potencjalnie za pośrednictwem jednej krawędzi wstecznej prowadzącej w górę.
Zainicjuj przy wejściu
Gdy DFS wchodzi do wierzchołka, ustaw jego disc i low na bieżącą wartość licznika, a następnie przejdź do jego sąsiadów.
disc[u] = low[u] = timer
timer += 1Warunek mostu
Po wywołaniu rekurencji dla dziecka v, jeśli low[v] > disc[u], żadna krawędź wsteczna nie omija u, więc krawędź u-v jest mostem.
if low[v] > disc[u]:
bridges.append((u, v))Warunek punktu artykulacji
Wierzchołek u, który nie jest korzeniem, jest punktem artykulacji, gdy dziecko v spełnia low[v] >= disc[u]: poddrzewo v nie może ominąć u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Szczególny przypadek korzenia
Korzeń DFS jest punktem artykulacji tylko wtedy, gdy ma co najmniej dwoje dzieci w drzewie DFS, dlatego należy je policzyć.
if parent[u] == -1 and children > 1:
art.add(u)Pomiń krawędź do rodzica
Podczas aktualizowania low na podstawie krawędzi wstecznej nie wracaj wzdłuż krawędzi do rodzica, bo błędnie oceniasz wtedy mosty.
if v != parent[u]:
low[u] = min(low[u], disc[v])Jedno przejście, dwa wyniki
Pojedynczy DFS znajduje jednocześnie wszystkie mosty i punkty artykulacji w czasie O(V + E). Nie jest potrzebne dodatkowe przejście.
Szybkie sprawdzenie
Po wywołaniu rekurencji dla dziecka v z wierzchołka u otrzymujesz low[v] > disc[u]. Co znaleziono?
Podsumowanie: krytyczne krawędzie i wierzchołki
Jeden DFS z wartościami disc i low znajduje wszystko: low[v] > disc[u] oznacza most, a low[v] >= disc[u] oznacza punkt artykulacji. 🌉
Często zadawane pytania
Czy lekcja „Mosty i punkty artykulacji” jest bezpłatna?
Tak — pełny tekst „Mosty i punkty artykulacji” 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 „Mosty i punkty artykulacji”?
Znajdowanie krawędzi i wierzchołków rozspajających graf Ć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 4 z 4.
Ile czasu zajmuje lekcja „Mosty i punkty artykulacji”?
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