Broer og artikulasjonspunkter
Finn kanter og noder som kobler grafen fra hverandre
Broer og artikulasjonspunkter er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Sårbare punkter i en graf
Noen deler av en ikke-rettet graf er kritiske: fjern dem, så faller grafen fra hverandre. Når du finner dem, avdekker du svake forbindelser.
Hva en bro er
En bro er en kant der antallet sammenhengende komponenter øker hvis kanten fjernes. Den er den eneste forbindelsen mellom to områder.
Hva et artikulasjonspunkt er
Et artikulasjonspunkt er en node der grafen blir usammenhengende hvis noden fjernes. Nettverk er sårbare for slike enkeltstående feilkilder.
DFS-trær igjen
Begge kjører én DFS og følger med på oppdagelsestid og en low-verdi, omtrent som Tarjan, men på en ikke-rettet graf.
disc = [-1] * n
low = [-1] * nLow angir lengst mulig rekkevidde bakover
En nodes low er den tidligste oppdagelses-ID-en som kan nås fra DFS-deltreet dens, eventuelt via én tilbakekant oppover.
Initialiser ved inngang
Når DFS går inn i en node, setter du disc og low til den gjeldende tidtakerverdien og går videre til naboene.
disc[u] = low[u] = timer
timer += 1Betingelsen for en bro
Etter rekursjonen inn i barn v er kanten u-v en bro hvis low[v] > disc[u], fordi ingen tilbakekant går forbi u.
if low[v] > disc[u]:
bridges.append((u, v))Betingelsen for et artikulasjonspunkt
En ikke-rotnode u er et artikulasjonspunkt når et barn v oppfyller low[v] >= disc[u]: Deltreet til v kan ikke gå utenom u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Det spesielle tilfellet med roten
DFS-roten er et artikulasjonspunkt bare hvis den har to eller flere barn i DFS-treet, så tell dem.
if parent[u] == -1 and children > 1:
art.add(u)Hopp over forelderens kant
Når du oppdaterer low fra en tilbakekant, må du ikke gå tilbake langs kanten til forelderen, ellers vurderer du broer feil.
if v != parent[u]:
low[u] = min(low[u], disc[v])Én gjennomgang, begge svarene
Én enkelt DFS finner alle broer og artikulasjonspunkter samtidig på O(V + E). Det trengs ingen ekstra gjennomgang.
Kort sjekk
Etter rekursjonen inn i barn v fra u finner du low[v] > disc[u]. Hva har du funnet?
Oppsummering: Kritiske kanter og noder
Én DFS med disc og low finner alt: low[v] > disc[u] markerer en bro, og low[v] >= disc[u] markerer et artikulasjonspunkt. 🌉
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Broer og artikulasjonspunkter» gratis?
Ja – hele teksten i «Broer og artikulasjonspunkter» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Broer og artikulasjonspunkter»?
Finn kanter og noder som kobler grafen fra hverandre Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Broer og artikulasjonspunkter»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Topologisk sortering med Kahns algoritme
- Finn sykluser i rettede grafer
- Sterkt sammenhengende komponenter
- Broer og artikulasjonspunkter