algorithm - 如何输出无向图的所有双连通分量？

Question

给定一个一般的无向图，我们如何在 O(N+M) 时间内打印出该图的所有双连通分量？我知道 Tarjan 的算法用于输出无向图的所有关节点，但我发现很难扩展该算法以打印双连通分量。我尝试搜索谷歌，但我得到的所有结果都不适用于我的测试用例，因为它们错过了算法的边缘情况。

有人可以提供这个问题的工作代码吗。

Def:双连通分量是一个连通子图，不包含顶点，删除顶点会断开子图。

编辑:我已经成功实现了 this link 中描述的算法由尼克拉斯提供。现在我有一个不同的问题，如何找出不包含边的无向图的子图，删除边会断开子图。请帮我解决这个备用问题。

Answer 1

这是一个classical problem with a known linear-time algorithm .不过，您可能需要先将图形分解为连接的组件。来自维基百科的算法描述:

The classic sequential algorithm for computing biconnected components in a connected undirected graph due to John Hopcroft andRobert Tarjan (1973) [1] runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions). The idea is to run a depth-first search while maintaining the following information: the depth of each vertex in the depth-first-search tree (once it gets visited), and for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called the lowpoint. The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of v, the depth of all neighbors of v (other than the parent of v in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree. The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children. Thus, it suffices to simply build one component out of each child subtree of the root (including the root).

可以在 http://www.cs.umd.edu/class/fall2005/cmsc451/biconcomps.pdf 找到一个很好的伪代码实现.