Comment puis-je trouver des ponts dans un graphe non orienté?

Question

Étant donné un graphique non orienté, comment puis-je trouver tous les ponts? J'ai seulement trouvé l'algorithme de Tarjan qui semble plutôt compliqué.

Il semble qu'il devrait y avoir plusieurs solutions de temps linéaire, mais je ne trouve rien.

Answer 1

L'algorithme de Tarjan était le premier algorithme de recherche de pont dans un graphe non orienté fonctionnant en temps linéaire. Cependant un algorithme plus simple existe et vous pouvez jeter un oeil à son implémentation here.

private int bridges;  // number of bridges 
    private int cnt;   // counter 
    private int[] pre;  // pre[v] = order in which dfs examines v 
    private int[] low;  // low[v] = lowest preorder of any vertex connected to v 

    public Bridge(Graph G) { 
     low = new int[G.V()]; 
     pre = new int[G.V()]; 
     for (int v = 0; v < G.V(); v++) low[v] = -1; 
     for (int v = 0; v < G.V(); v++) pre[v] = -1; 

     for (int v = 0; v < G.V(); v++) 
      if (pre[v] == -1) 
       dfs(G, v, v); 
    } 

    public int components() { return bridges + 1; } 

    private void dfs(Graph G, int u, int v) { 
     pre[v] = cnt++; 
     low[v] = pre[v]; 
     for (int w : G.adj(v)) { 
      if (pre[w] == -1) { 
       dfs(G, v, w); 
       low[v] = Math.min(low[v], low[w]); 
       if (low[w] == pre[w]) { 
        StdOut.println(v + "-" + w + " is a bridge"); 
        bridges++; 
       } 
      } 

      // update low number - ignore reverse of edge leading to v 
      else if (w != u) 
       low[v] = Math.min(low[v], pre[w]); 
     } 
    } 

L'algorithme effectue le travail en conservant 2 tableaux pré et bas. prétient la numérotation des parcours de pré-commande pour les nœuds. Donc, pre [0] = 2 signifie que le vertex 0 a été découvert dans le 3ème appel dfs. Et low [u] contient le plus petit numéro de pré-ordre de n'importe quel sommet accessible depuis u.

L'algorithme détecte un pont chaque fois que pour un front u - v, où u vient en premier dans la numérotation de précommande, low [v] == pre [v]. C'est parce que si nous enlevons le bord entre u - v, v ne peut atteindre aucun sommet qui vient avant u. Ainsi, la suppression du bord diviserait le graphique en 2 graphiques distincts.

Pour une explication plus détaillée, vous pouvez également regarder this answer.