连接图中的桥梁
我有一个编程任务（不是家庭作业），我必须在图表中find桥梁。 我自己做了一些，但是不能拿出任何令人满意的结果。 所以我GOOGLE了，我find了一些东西，但我无法理解算法，因为它是呈现。 有人可以看看这个代码，给我一个解释。
public Bridge(Graph G) { low = new int[GV()]; pre = new int[GV()]; for (int v = 0; v < GV(); v++) low[v] = -1; for (int v = 0; v < GV(); v++) pre[v] = -1; for (int v = 0; v < GV(); 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]); } } Def：桥是一个边，当被移除时，将断开图（或者将连接的组件数增加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和prearrays。 数组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)这次将是假的。 所以，你会输入其他部分。 那里的if语句检查B是否是D的父顶点。 不是的，所以D会把B的价值吸收到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]);通过代码low[v] = Math.min(low[v], low[w]);传播回到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本身。
希望这个解释有帮助。
不是一个新的答案，但我需要在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递归深度限制器...
不是一个新的答案，但我需要这个JVM / Kotlin。 这是一个依赖于com.google.common.graph.Graph的翻译。
/** * [T] The type of key held in the [graph]. */ private class BridgeComputer(private val graph: ImmutableGraph ) { /** * Counter. */ private var count = 0 /** * `low[v]` = Lowest preorder of any vertex connected to `v`. */ private val low: MutableMap = graph.nodes().map { it to -1 }.toMap(mutableMapOf()) /** * `pre[v]` = Order in which [depthFirstSearch] examines `v`. */ private val pre: MutableMap = graph.nodes().map { it to -1 }.toMap(mutableMapOf()) private val foundBridges = mutableSetOf>() 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)!! }
希望这会让别人的生活更轻松。