如何在无向图中找到桥? [英] How can I find bridges in an undirected graph?
问题描述
给定一个无向图,我怎样才能找到所有的桥?我只发现了 Tarjan 的算法,它看起来相当复杂.
Given an undirected Graph, how can I find all the bridges? I've only found Tarjan's algorithm which seems rather complicated.
似乎应该有多个线性时间解决方案,但我找不到任何东西.
It seems there should be multiple linear time solutions, but I can't find anything.
推荐答案
Tarjan 算法是第一个在线性时间内运行的无向图中的找桥算法.但是,存在更简单的算法,您可以在此处查看其实现.
Tarjan's algorithm was the first bridge finding algorithm in an undirected graph that ran in linear time. However a simpler algorithm exists and you can have a look at its implementation here.
private int bridges; // number of bridges
private int cnt; // counter
private int[] pre; // pre[v] = order in which dfs examines v
private int[] low; // low[v] = lowest preorder of any vertex connected to v
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]);
}
}
该算法通过维护 2 个数组 pre 和 low 来完成这项工作.pre 保存节点的前序遍历编号.所以 pre[0] = 2 意味着在第三次 dfs 调用中发现了顶点 0.而 low[u] 持有从 u 可达的任何顶点的最小预序数.
该算法在任何时候检测到一条边 u--v 的桥,其中 u 在预序编号中排在第一位,low[v]==pre[v].这是因为如果我们移除 u--v 之间的边,v 将无法到达 u 之前的任何顶点.因此,去除边会将图分成 2 个单独的图.
The algorithm does the job by maintaining 2 arrays pre and low. pre holds the pre-order traversal numbering for the nodes. So pre[0] = 2 means that vertex 0 was discovered in the 3rd dfs call. And low[u] holds the smallest pre-order number of any vertex that is reachable from u.
The algorithm detects a bridge whenever for an edge u--v, where u comes first in the preorder numbering, low[v]==pre[v]. This is because if we remove the edge between u--v, v can't reach any vertex that comes before u. Hence removing the edge would split the graph into 2 separate graphs.
更详细的解释你也可以看看这个答案 .
For a more elaborate explanation you can also have a look at this answer .
这篇关于如何在无向图中找到桥?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!