接続されたグラフ内のブリッジ

Question

私はグラフでブリッジを見つけなければならないプログラミングタスク（宿題ではありません）があります。私は少し自分でそれに取り組んだが、満足できるものは何も出てこなかった。だから私はそれを見つけた、私は何かを見つけたが、私はそれが提示されているアルゴリズムを理解することができません。誰かがこのコードを見て、私に説明をしてくださいでしたか？

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：削除するとエッジを削除するとグラフが切断されます（または接続されたコンポーネントの数が1増加します）。

グラフの橋についての1つの観察;ループに属する辺のいずれもブリッジではありません。したがって、A--B--C--Aなどのグラフでは、エッジA--B,B--C、C--Aのいずれかを削除しても、グラフは切断されません。しかし、無向グラフの場合、エッジA--BはB--Aを意味します。このエッジは依然としてブリッジになる可能性があり、そこにある唯一のループはA--B--Aです。したがって、バックエッジによって形成されたループのみを考慮する必要があります。これは、関数の引数に渡した親情報が役立つところです。 A--B--Aなどのループを使用しないようにします。

ここで、背面エッジ（またはループ）を特定するために、lowおよびpreアレイを使用します。配列preは、dfsアルゴリズムのvisited配列と似ています。訪問した頂点に単にフラグを立てるのではなく、（頂点の位置に応じて）異なる頂点を識別します。 low配列は、ループがあるかどうかを識別するのに役立ちます。 lowアレイは、現在の頂点が到達可能な最も低い番号の（preアレイからの）頂点を識別する。

このグラフA--B--C--D--Bで作業できます。

この時点で

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 

から開始して、あなたは、グラフ内のサイクル/ループが発生しました。あなたのコードでif (pre[w] == -1)は今回はfalseになります。だから、あなたはelse部分を入力します。 ifステートメントは、Bが親頂点であるかどうかを確認します。Dです。そうではないので、DはBのpre値をlowに吸収します。例を続けると、Dの

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

このlow値は、コードlow[v] = Math.min(low[v], low[w]);介しCに戻って伝播します。

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 

さて、サイクル/ループが識別されていることを、我々は頂点Aがループの一部ではないことに注意してください。したがって、あなたは橋としてA--Bを印刷します。コードlow['B'] == pre['B']は、Bへのエッジを意味するブリッジを意味します。これは、Bから到達できる最下位の頂点がBであるためです。

この説明は役立ちます。

Answer 2

新しい答えではありませんが、これはPythonで必要でした。ここでは無向NetworkX Graphオブジェクト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 

が大きいグラフのPythonの再帰の深さ制限に注意してください...

Answer 3

ていない新たな答えは、私はJVMのためにこれを必要と/コトリン。ここには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)!! 
} 

これによって、誰かの人生がより楽になることを願っています。