Ponts et points d’articulation
Trouver les arêtes et les nœuds qui déconnectent le graphe
Ponts et points d’articulation est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Zones fragiles d’un graphe
Certaines parties d’un graphe non orienté sont critiques : retirez-les et le graphe se divise. Les trouver révèle les liaisons fragiles.
Définition d’un pont
Un pont est une arête dont la suppression augmente le nombre de composantes connexes. Elle constitue l’unique chemin entre deux régions.
Définition d’un point d’articulation
Un point d’articulation est un nœud dont la suppression déconnecte le graphe. Les réseaux redoutent ces points de défaillance uniques.
Les arbres DFS, encore une fois
Les deux algorithmes s’appuient sur un seul DFS et suivent le temps de découverte ainsi qu’une valeur low, un peu comme Tarjan, mais sur un graphe non orienté.
disc = [-1] * n
low = [-1] * nLow indique la portée la plus lointaine
Le low d’un nœud est le plus petit identifiant de découverte accessible depuis son sous-arbre DFS, éventuellement par une seule arête de retour vers le haut.
Initialiser à l’entrée
Lorsque DFS entre dans un nœud, attribuez à son disc et à son low la valeur du compteur actuel, puis poursuivez vers ses voisins.
disc[u] = low[u] = timer
timer += 1La condition d’un pont
Après être descendu récursivement dans l’enfant v, si low[v] > disc[u], aucune arête de retour ne contourne u : l’arête u-v est donc un pont.
if low[v] > disc[u]:
bridges.append((u, v))La condition d’un point d’articulation
Un nœud u qui n’est pas une racine est un point d’articulation lorsqu’un enfant v vérifie low[v] >= disc[u] : le sous-arbre de v ne peut pas contourner u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)Le cas particulier de la racine
La racine de DFS est un point d’articulation uniquement si elle possède au moins deux enfants dans l’arbre DFS : comptez-les.
if parent[u] == -1 and children > 1:
art.add(u)Ignorer l’arête vers le parent
Lors de la mise à jour de low à partir d’une arête de retour, ne repartez pas le long de l’arête vers votre parent, sinon vous évaluerez mal les ponts.
if v != parent[u]:
low[u] = min(low[u], disc[v])Une passe, deux résultats
Un seul DFS trouve simultanément tous les ponts et les points d’articulation en O(V + E). Aucun parcours supplémentaire n’est nécessaire.
Vérification rapide
Après être descendu récursivement dans l’enfant v depuis u, vous trouvez low[v] > disc[u]. Qu’avez-vous trouvé ?
Récapitulatif : arêtes et nœuds critiques
Un seul DFS avec disc et low suffit : low[v] > disc[u] signale un pont, et low[v] >= disc[u] signale un point d’articulation. 🌉
Questions Fréquemment Posées
La leçon « Ponts et points d’articulation » est-elle gratuite ?
Oui — le texte complet de « Ponts et points d’articulation » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Ponts et points d’articulation » ?
Trouver les arêtes et les nœuds qui déconnectent le graphe Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Ponts et points d’articulation » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Tri topologique avec l’algorithme de Kahn
- Détecter les cycles dans les graphes orientés
- Composantes fortement connexes
- Ponts et points d’articulation