Puentes en un gráfico conectado

Question

Tengo una tarea de programación (no tarea) donde tengo que encontrar los puentes en un gráfico. Yo mismo trabajé un poco, pero no pude encontrar nada satisfactorio. Así que busqué en Google, encontré algo, pero no puedo entender el algoritmo tal como se presenta. ¿Podría alguien echar un vistazo a este código y darme una explicación?

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]); 
    } 
} 

Answer 1

Def: El puente es una ventaja, cuando se retiran, se desconectará la gráfica (o aumentar el número de componentes conectados por 1).

Una observación sobre puentes en gráfico; ninguno de los bordes que pertenecen a un bucle puede ser un puente. Por lo tanto, en un gráfico como A--B--C--A, la eliminación de cualquiera de los bordes A--B, B--C y C--A no desconectará el gráfico. Pero, para un gráfico no dirigido, el borde A--B implica B--A; y este borde aún podría ser un puente, donde el único bucle en el que se encuentra es A--B--A. Entonces, deberíamos considerar solo esos bucles formados por un borde posterior. Aquí es donde ayuda la información principal que ha pasado en el argumento de la función. Le ayudará a no utilizar los bucles como A--B--A.

Ahora para identificar el borde posterior (o el bucle), A--B--C--A utilizamos las matrices low y pre. La matriz pre es como la matriz visited en el algoritmo dfs; pero en lugar de marcar solo el vértice como visitado, identificamos cada vértice con un número diferente (según su posición en el árbol dfs). La matriz low ayuda a identificar si hay un bucle. La matriz low identifica el vértice con el número más bajo (desde pre) que puede alcanzar el vértice actual.

Permite trabajar a través de este gráfico A--B--C--D--B.

A partir de una

dfs: ^    ^    ^    ^   ^
pre: 0 -1 -1 -1 -1 0--1 -1 -1 1 0--1--2 -1 1 0--1--2--3 1 0--1--2--3--1 
graph: A--B--C--D--B A--B--C--D--B A--B--C--D--B A--B--C--D--B A--B--C--D--B 
low: 0 -1 -1 -1 -1 0--1 -1 -1 1 0--1--2 -1 1 0--1--2--3 1 0--1--2--3->1 

En este punto, le ha surgido un ciclo/bucle en el gráfico. En su código if (pre[w] == -1) será falso esta vez. Entonces, ingresarás a la parte else. La instrucción if allí está comprobando si B es el vértice padre de D. No lo es, por lo que D absorberá Bpre valor en low. Continuando con el ejemplo,

dfs:   ^
pre: 0--1--2--3 
graph: A--B--C--D 
low: 0--1--2--1 

Este valor low de D se propaga de nuevo a través del código Clow[v] = Math.min(low[v], low[w]);.

dfs:  ^  ^  ^
pre: 0--1--2--3--1 0--1--2--3--1 0--1--2--3--1 
graph: A--B--C--D--B A--B--C--D--B A--B--C--D--B 
low: 0--1--1--1--1 0--1--1--1--1 0--1--1--1--1 

Ahora, que se identifica el ciclo/bucle, observamos que el vértice A no es parte del bucle. Por lo tanto, imprime A--B como un puente. El código low['B'] == pre['B'] significa que un borde a B será un puente. Esto es porque, el vértice más bajo que podemos alcanzar desde B es B.

Espero que esta explicación ayude.

Answer 2

No es una respuesta nueva, pero la necesitaba en Python.He aquí una traducción del algoritmo para un no dirigido objeto NetworkX Gráfico G:

def bridge_dfs(G,u,v,cnt,low,pre,bridges): 
    cnt += 1 
    pre[v] = cnt 
    low[v] = pre[v] 

    for w in nx.neighbors(G,v): 
     if (pre[w] == -1): 
      bridge_dfs(G,v,w,cnt,low,pre,bridges) 

      low[v] = min(low[v], low[w]) 
      if (low[w] == pre[w]): 
       bridges.append((v,w)) 

     elif (w != u): 
      low[v] = min(low[v], pre[w]) 

def get_bridges(G): 
    bridges = [] 
    cnt  = 0 
    low  = {n:-1 for n in G.nodes()} 
    pre  = low.copy() 

    for n in G.nodes(): 
     bridge_dfs(G, n, n, cnt, low, pre, bridges) 

    return bridges # <- List of (node-node) tuples for all bridges in G 

Tenga cuidado de limitador de nivel de recursividad de Python para grandes gráficos ...

Answer 3

No

una nueva respuesta, pero necesitaba esto para la JVM/Kotlin. Aquí hay una traducción que se basa en com.google.common.graph.Graph.

/** 
* [T] The type of key held in the [graph]. 
*/ 
private class BridgeComputer<T>(private val graph: ImmutableGraph<T>) { 
    /** 
    * Counter. 
    */ 
    private var count = 0 
    /** 
    * `low[v]` = Lowest preorder of any vertex connected to `v`. 
    */ 
    private val low: MutableMap<T, Int> = 
     graph.nodes().map { it to -1 }.toMap(mutableMapOf()) 
    /** 
    * `pre[v]` = Order in which [depthFirstSearch] examines `v`. 
    */ 
    private val pre: MutableMap<T, Int> = 
     graph.nodes().map { it to -1 }.toMap(mutableMapOf()) 

    private val foundBridges = mutableSetOf<Pair<T, T>>() 

    init { 
     graph.nodes().forEach { v -> 
      // DO NOT PRE-FILTER! 
      if (pre[v] == -1) { 
       depthFirstSearch(v, v) 
      } 
     } 
    } 

    private fun depthFirstSearch(u: T, v: T) { 
     pre[v] = count++ 
     low[v] = checkNotNull(pre[v]) { "pre[v]" } 
     graph.adjacentNodes(v).forEach { w -> 
      if (pre[w] == -1) { 
       depthFirstSearch(v, w) 
       low[v] = 
        Math.min(checkNotNull(low[v]) { "low[v]" }, checkNotNull(low[w]) { "low[w]" }) 
       if (low[w] == pre[w]) { 
        println("$v - $w is a bridge") 
        foundBridges += (v to w) 
       } 
      } else if (w != u) { 
       low[v] = 
        Math.min(checkNotNull(low[v]) { "low[v]" }, checkNotNull(pre[w]) { "pre[w]" }) 
      } 
     } 
    } 

    /** 
    * Holds the computed bridges. 
    */ 
    fun bridges() = ImmutableSet.copyOf(foundBridges)!! 
} 

Esperamos que esto hace más fácil la vida de alguien.