Ponti in un grafico collegato

Question

Ho un compito di programmazione (non i compiti a casa.) Dove devo trovare i ponti in un grafico. Ci ho lavorato un po ', ma non sono riuscito a trovare nulla di soddisfacente. Così ho cercato su google, ho trovato qualcosa ma non sono in grado di capire l'algoritmo così come viene presentato. Qualcuno potrebbe dare un'occhiata a questo codice e darmi una spiegazione?

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: Bridge è un bordo, quando rimosso, disconnetterà il grafico (o aumenterà il numero di componenti collegati di 1).

Un'osservazione riguardante i ponti nel grafico; nessuno dei bordi che appartengono a un loop può essere un ponte. Pertanto, in un grafico come A--B--C--A, la rimozione di qualsiasi spigolo A--B, B--C e C--A non scollegherà il grafico. Ma, per un grafico non orientato, il limite A--B implica B--A; e questo bordo potrebbe essere ancora un ponte, in cui l'unico anello in cui si trova è A--B--A. Quindi, dovremmo considerare solo quei loop formati da un bordo posteriore. Qui è dove le informazioni genitore che hai passato nell'argomento funzione aiutano. Ti aiuterà a non usare i loop come A--B--A.

Ora per identificare il bordo posteriore (o il loop), A--B--C--A utilizziamo gli array low e pre. L'array pre è come l'array visited nell'algoritmo dfs; ma invece di segnalare semplicemente il vertice come visitato, identifichiamo ciascun vertice con un numero diverso (in base alla sua posizione nell'albero dfs). L'array low consente di identificare se esiste un ciclo. L'array low identifica il vertice con il numero più basso (da pre) che il vertice corrente può raggiungere.

Consente di lavorare con questo grafico A--B--C--D--B.

a partire da un

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 

A questo punto, hai incontrato un ciclo/ciclo sul grafico. Nel tuo codice if (pre[w] == -1) questa volta sarà falso. Quindi, entrerai nella parte else. L'istruzione if sta verificando se B è il vertice principale di D. Non lo è, quindi D assorbirà il valore di pre in low. Continuando l'esempio,

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

Questo valore low di D si propaga all'indietro fino C attraverso il codice low[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 

Ora, che il ciclo/ciclo viene identificato, si nota che il vertice A non fa parte del ciclo. Quindi, stampa A--B come un ponte. Il codice low['B'] == pre['B'] indica che un fronte a B sarà un bridge. Questo perché il vertice più basso che possiamo raggiungere da B è lo stesso B.

Spero che questa spiegazione aiuti.

Answer 2

Non una nuova risposta, ma avevo bisogno di questo in Python.Ecco una traduzione del algoritmo per un oggetto non orientato NetworkX Grafico 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 

Fare attenzione di limitatore di profondità di ricorsione di Python per i grandi grafici ...

Answer 3

Non una nuova risposta, ma avevo bisogno di questo per la JVM/Kotlin. Ecco una traduzione che si basa su 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)!! 
} 

Speriamo che questo semplifichi la vita a qualcuno.