連接圖中的網橋

Question

我有一個編程任務（不是家庭作業），我必須在圖中找到網橋。我自己做了一些工作，但不能滿足任何需求。所以我GOOGLE了它，我找到了一些東西，但我無法理解算法，因爲它是呈現。有人可以看看這段代碼，並給我一個解釋。？

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

定義：橋是一個邊，當被移除時，將斷開圖（或增加連接組件數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數組;但不是隻標記頂點被訪問，而是用不同的數字標識每個頂點（根據它在dfs樹中的位置）。 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)這次將是假的。所以，你會輸入其他部分。 if語句檢查B是否爲D的父頂點。它不是，所以D將吸收B的pre值爲low。繼續該示例，

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

的D這low值傳播回C通過代碼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 

，該週期/循環被確定，我們注意到，頂點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)!! 
} 

希望這會讓別人的生活更輕鬆。