连接图中的桥梁

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

- frodo

---

你缺少了 Graph 类。它在哪里可以找到？ - jedwards

我没有在这里放置图形类。我很难理解如何找到桥梁。该图以邻接表的形式实现。 - frodo

@jedwards，Graph类的链接为http://algs4.cs.princeton.edu/41undirected/Graph.java.html。 - Denis

Answer 1

定义：桥是一条边，当移除它时，会使图断开连接（或使连接分量的数量增加1）。

关于图中桥的一个观察：任何属于环的边都不可能是桥。因此，在像A--B--C--A这样的图中，删除任何一条边A--B、B--C和C--A都不会使图断开连接。但对于无向图，边A--B也意味着B--A；而这条边仍然可以成为桥，其唯一所在的环是A--B--A。因此，我们应该只考虑由反向边形成的环。这就是函数参数中传递的父节点信息有助于避免使用如A--B--A这样的循环的地方。

现在要识别反向边（或者循环），例如A--B--C--A，我们使用low和pre数组。数组pre类似于dfs算法中的visited数组；但是，我们不仅将顶点标记为已访问，而且还根据其在dfs树中的位置将每个顶点标识为不同的数字。数组low有助于确定是否存在循环。数组low识别当前顶点可以到达的编号最低的（来自pre数组）顶点。

让我们通过这个图A--B--C--D--B来进行演示。

从A开始：

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 中。继续上面的例子，

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

这个D的低值通过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本身。希望这个解释有所帮助。

- deebee

---

这个可视化图表对我非常有帮助！其他网站都没什么用！谢谢@deebee - Aviral Srivastava

Answer 2

虽然这不是一个新的答案，但我需要用Python实现。下面是对于无向 NetworkX 图对象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对于大图的递归深度限制器...

- gerowam

Answer 3

虽然这不是一个新的答案，但我需要它来处理JVM/Kotlin。以下是一种依赖于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)!!
}

希望这能让某些人的生活更轻松。

- Jonathan Leitschuh

Answer 4

假设给你一条边(c,d)，你需要判断它是否是桥。
有几种方法可以解决这个问题，但让我们专注其中一种。

• 从c开始，执行BFS。
• 如果存在边c-d，则不要访问它。
• 通过将一个布尔类型的visited标记来跟踪顶点。

最后，如果你发现d被访问了，这意味着从源c仍然可以访问d，因此c-d不是桥梁。 以下是上述内容的简短实现：

int isBridge(int V, ArrayList<ArrayList<Integer>> adj,int c,int d)
{
    Queue<Integer> q = new LinkedList<>();
    boolean visited[] = new boolean[V];
    ArrayList<Integer> ls = new ArrayList<>();
    
    q.add(c);
    
    while(!q.isEmpty()) {
        
        Integer v = q.remove();
        
        if(visited[v])
            continue;

        visited[v] = true;
        ls.add(v);
        
        for(Integer e: adj.get(v)) {
            
            if(visited[e] || (c == v && d == e))
                continue;
            q.add(e);
        }
    }
    
    if(visited[d] == true)
        return 0;
    return 1;
    
}

- Nirbhay Kumar Nachiketa