Détecteur de Ponts

Pseudocode

Exactement la même machinerie que pour les points d'articulation, avec une seule comparaison changée de supérieur ou égal en strictement supérieur.

dfs(u, parent):
    dec[u] = low[u] = ++temps

    pour chaque voisin v de u:
        si v == parent: continuer   // sauter l arete d arrivee
        si v deja visite:
            low[u] = min(low[u], dec[v])    // arete arriere
        sinon:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            si low[v] > dec[u]:
                signaler l arete (u, v) comme pont

L'inégalité stricte fait toute la différence avec les points d'articulation. low[v] > dec[u] signifie que rien dans le sous-arbre situé sous v ne peut atteindre u ni quoi que ce soit au-dessus, l'arête (u, v) est donc l'unique route et son retrait déconnecte le graphe. Les points d'articulation utilisent low[v] >= dec[u], où l'égalité signifie que le sous-arbre atteint u lui-même mais pas au-delà; cela isole le sous-arbre si tu supprimes le sommet u, mais pas si tu supprimes seulement l'arête.

Exemple détaillé, étape par étape

Exécute le DFS depuis A sur un triangle prolongé par une queue de deux arêtes, le graphe déjà utilisé pour les points d'articulation, afin de comparer les deux tests sur des données identiques.

Graphe d'exemple: Arêtes non orientées A-B, B-C et C-A formant un triangle, plus C-D et D-E.

1. Attribuer les dates de découverte. La descente par A, B, C, D puis E donne les dates de découverte 1, 2, 3, 4 et 5 respectivement.
2. E est une impasse. E n'a que son parent D pour voisin, donc low[E] reste à 5.
3. D-E est un pont. De retour en D, low[D] = min(4, low[E] = 5) = 4. Teste l'arête: low[E] = 5 > dec[D] = 4, donc D-E est un pont. Son retrait isole E, ce qui est manifestement correct.
4. C-D est aussi un pont. En C, l'arête arrière C-A donne low[C] = min(3, dec[A] = 1) = 1, et en intégrant le fils on obtient min(1, low[D] = 4) = 1. Teste l'arête vers D: low[D] = 4 > dec[C] = 3, donc C-D est également un pont.
5. Les arêtes du triangle ne le sont pas. En B, low[B] = min(2, low[C] = 1) = 1. Teste l'arête B-C: low[C] = 1 > dec[B] = 2 est faux, donc B-C n'est pas un pont. C peut atteindre A sans emprunter B-C, l'arête dispose donc d'une route alternative. Le même raisonnement écarte A-B et C-A.

Les ponts sont C-D et D-E. Note le contraste avec les points d'articulation sur ce même graphe, où la réponse était les sommets C et D. Chaque arête du triangle appartient à un cycle et dispose donc d'un détour, tandis que chaque arête de la queue est l'unique connexion vers tout ce qui se trouve au-delà. La règle générale en découle directement: une arête est un pont exactement lorsqu'elle n'appartient à aucun cycle.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Un unique parcours en profondeur avec un travail supplémentaire constant par arête, le coût est donc celui du parcours. Chaque sommet est visité une fois et chaque arête examinée deux fois, une depuis chaque extrémité. L'état tient en deux entiers par sommet plus la pile de récursion, le tout en O(V). L'approche naïve consistant à retirer chaque arête puis à tester la connexité coûte O(E fois (V + E)); sur un graphe de 10 000 arêtes, la méthode du low-link est donc environ quatre ordres de grandeur plus rapide.

Quand utiliser Recherche de Ponts, et quand l'éviter

Le même DFS répond à plusieurs questions voisines. Choisis selon que l'élément fragile est une arête, un sommet ou toute une région.

Pièges fréquents

• Utiliser >= au lieu de >. Le test des points d'articulation est low[v] >= dec[u]; celui des ponts est strictement low[v] > dec[u]. Utiliser >= signale toute arête d'arbre menant à un sommet incapable de remonter au-dessus de son parent, ce qui sur-signale gravement. Un seul caractère sépare les deux algorithmes.
• Sauter le parent par sommet plutôt que par arête. Avec des arêtes parallèles entre u et v, la seconde arête constitue une véritable route alternative et aucune des deux n'est un pont. Sauter par identité de sommet masque ce fait et signale un pont inexistant. Mémorise l'arête précise empruntée à l'arrivée.
• Utiliser low[v] plutôt que dec[v] pour les arêtes arrière. Lorsque tu rencontres un voisin déjà visité, intègre sa date de découverte, pas son low-link. Utiliser low[v] peut importer une valeur venue d'un sous-arbre sans rapport et supprimer silencieusement de véritables ponts.
• L appliquer à des graphes orientés. Les ponts sont définis pour les graphes non orientés. La question orientée, savoir quelles arêtes augmentent le nombre de composantes fortement connexes lorsqu'on les retire, est un autre problème nécessitant d'autres outils.
• Oublier les composantes déconnectées. Un DFS ne couvre qu'une composante. Itère sur tous les sommets et lance une nouvelle recherche depuis chacun de ceux non visités, sinon les ponts des autres composantes resteront non signalés.

Questions fréquentes

Qu'est-ce qu'un pont dans un graphe?

Un pont, aussi appelé arête de coupe, est une arête dont le retrait augmente le nombre de composantes connexes. De manière équivalente, c'est une arête qui n'appartient à aucun cycle: s'il existait un cycle la traversant, le reste de ce cycle offrirait une route alternative et son retrait ne déconnecterait rien.

Comment trouve-t-on les ponts dans un graphe?

Exécute un unique DFS en enregistrant pour chaque sommet sa date de découverte et son low-link, c'est-à-dire la plus petite date de découverte atteignable depuis son sous-arbre via au plus une arête arrière. Une arête d'arbre allant de u au fils v est un pont exactement lorsque low[v] > dec[u], c'est-à-dire lorsque rien sous v ne peut atteindre u ni au-dessus. L'algorithme complet tient en O(V + E).

Quelle est la différence entre un pont et un point d'articulation?

Un pont est une arête dont le retrait déconnecte le graphe; un point d'articulation est un sommet produisant le même effet. Les deux découlent du même DFS et diffèrent par une comparaison: strictement supérieur pour les ponts, supérieur ou égal pour les points d'articulation. Un graphe peut posséder l'un sans l'autre.

Un pont peut-il faire partie d un cycle?

Non, et c'est la façon la plus claire de se le représenter. Si une arête appartient à un cycle, le reste de ce cycle constitue un chemin alternatif entre ses extrémités, si bien que son retrait laisse le graphe connexe. Les ponts sont exactement les arêtes qui n'appartiennent à aucun cycle.

À quoi servent les ponts?

À repérer les liens critiques des dorsales de télécommunications et de fibre, les routes et tronçons ferroviaires indispensables dont la fermeture scinderait une région, les connexions fragiles des réseaux électriques, et à analyser le risque des dépendances logicielles. Sur LeetCode, le même problème apparaît sous le nom de Critical Connections in a Network.