Broer og artikulationspunkter
Find kanter og knuder, der afkobler grafen
Broer og artikulationspunkter er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Skrøbelige steder i en graf
Nogle dele af en urettet graf er kritiske: fjern dem, og grafen falder fra hinanden. Hvis du finder dem, afslører du de svage forbindelser.
Hvad en bro er
En bro er en kant, hvis fjernelse øger antallet af sammenhængende komponenter. Den er den eneste vej mellem to områder.
Hvad et artikulationspunkt er
Et artikulationspunkt er en knude, hvis fjernelse gør grafen usammenhængende. Netværk er sårbare over for disse enkelte fejlpunkter.
DFS-træer igen
Begge algoritmer kører på én DFS og følger opdagelsestidspunkt og en low-værdi, meget ligesom Tarjan, men på en urettet graf.
disc = [-1] * n
low = [-1] * nLow betyder længst tilbage
En knudes low er det tidligste opdagelses-id, der kan nås fra dens DFS-deltræ, muligvis via én bagkant opad.
Initialiser ved indgangen
Når DFS går ind i en knude, skal du sætte dens disc og low til den aktuelle tidsværdi og gå videre til dens naboer.
disc[u] = low[u] = timer
timer += 1Betingelsen for en bro
Efter du rekursivt har besøgt barn v, gælder det, at hvis low[v] > disc[u], springer ingen bagkant forbi u, så kanten u-v er en bro.
if low[v] > disc[u]:
bridges.append((u, v))Betingelsen for et artikulationspunkt
En ikke-rodknude u er et artikulationspunkt, når et barn v opfylder low[v] >= disc[u]: Deltræet under v kan ikke gå uden om u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Det særlige tilfælde for roden
DFS-roden er kun et artikulationspunkt, hvis den har mindst to børn i DFS-træet, så tæl dem.
if parent[u] == -1 and children > 1:
art.add(u)Spring forældre-kanten over
Når du opdaterer low fra en bagkant, må du ikke gå tilbage ad kanten til din forælder, ellers vurderer du broer forkert.
if v != parent[u]:
low[u] = min(low[u], disc[v])Ét gennemløb, begge svar
Én enkelt DFS finder alle broer og artikulationspunkter sammen i O(V + E). Der er ikke brug for et ekstra gennemløb.
Hurtigt tjek
Efter du rekursivt har besøgt barn v fra u, finder du low[v] > disc[u]. Hvad har du fundet?
Opsummering: Kritiske kanter og knuder
Én DFS med disc og low finder det hele: low[v] > disc[u] markerer en bro, og low[v] >= disc[u] markerer et artikulationspunkt. 🌉
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Broer og artikulationspunkter” gratis?
Ja — hele teksten til “Broer og artikulationspunkter” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Broer og artikulationspunkter”?
Find kanter og knuder, der afkobler grafen Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Broer og artikulationspunkter”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Topologisk sortering med Kahns algoritme
- Find cyklusser i rettede grafer
- Stærkt sammenhængende komponenter
- Broer og artikulationspunkter