Ponti e punti di articolazione
Trovare gli archi e i nodi che disconnettono il grafo
Ponti e punti di articolazione è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
I punti fragili di un grafo
Alcune parti di un grafo non orientato sono critiche: rimuovendole, il grafo si separa. Trovarle permette di individuare i collegamenti deboli.
Che cos'è un ponte
Un ponte è un arco la cui rimozione aumenta il numero di componenti connesse. È l'unico percorso tra due regioni.
Che cos'è un punto di articolazione
Un punto di articolazione è un nodo la cui rimozione disconnette il grafo. Le reti sono vulnerabili a questi singoli punti di guasto.
Di nuovo gli alberi DFS
Entrambi gli algoritmi si basano su un'unica DFS e tengono traccia del tempo di scoperta e di un valore low, in modo simile a Tarjan, ma su un grafo non orientato.
disc = [-1] * n
low = [-1] * nLow indica la portata massima
Il valore low di un nodo è il primo identificatore di scoperta raggiungibile dal suo sottoalbero DFS, eventualmente attraverso un arco all'indietro verso l'alto.
Inizializzare all'ingresso
Quando la DFS entra in un nodo, si impostano disc e low sul valore attuale del timer e si prosegue verso i vicini.
disc[u] = low[u] = timer
timer += 1La condizione per un ponte
Dopo la ricorsione sul figlio v, se low[v] > disc[u], nessun arco all'indietro supera u, quindi l'arco u-v è un ponte.
if low[v] > disc[u]:
bridges.append((u, v))La condizione per un punto di articolazione
Un nodo u non radice è un punto di articolazione quando un figlio v soddisfa low[v] >= disc[u]: il sottoalbero di v non può aggirare u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Il caso speciale della radice
La radice della DFS è un punto di articolazione solo se ha almeno due figli nell'albero DFS, quindi è necessario contarli.
if parent[u] == -1 and children > 1:
art.add(u)Ignorare l'arco verso il padre
Quando si aggiorna low da un arco all'indietro, non si deve tornare indietro lungo l'arco verso il proprio padre, altrimenti si valuterebbero erroneamente i ponti.
if v != parent[u]:
low[u] = min(low[u], disc[v])Un passaggio, due risultati
Una singola DFS trova contemporaneamente tutti i ponti e i punti di articolazione in O(V + E). Non serve alcuna visita aggiuntiva.
Verifica rapida
Dopo la ricorsione sul figlio v a partire da u, si trova low[v] > disc[u]. Che cosa si è trovato?
Riepilogo: archi e nodi critici
Una sola DFS con disc e low trova tutto: low[v] > disc[u] indica un ponte, mentre low[v] >= disc[u] indica un punto di articolazione. 🌉
Domande Frequenti
La lezione «Ponti e punti di articolazione» è gratuita?
Sì — il testo completo di «Ponti e punti di articolazione» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Ponti e punti di articolazione»?
Trovare gli archi e i nodi che disconnettono il grafo Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Ponti e punti di articolazione»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ordinamento topologico con l’algoritmo di Kahn
- Rilevare cicli nei grafi orientati
- Componenti fortemente connesse
- Ponti e punti di articolazione