Nik*_*nka 10 algorithm graph-theory depth-first-search data-structures
给定一般的无向图,我们如何在O(N + M)时间内打印图的所有双连通分量？我知道Tarjan的算法用于输出无向图的所有关节点,但我发现很难扩展算法来打印双连通组件.我尝试搜索谷歌,但我得到的所有结果都不适用于我的测试用例,因为他们错过了算法的边缘情况.
有人可以提供这个问题的工作代码.
Def:双连通组件是一个连接子图,不包含顶点,删除会断开子图.
编辑:我已成功实施了Niklas提供的此链接中所述的算法.现在我有一个不同的问题,我怎样才能找到一个无向图的子图,其中没有边删除会断开子图.请帮我解决这个替代问题.
这是已知线性时间算法的经典问题.但是,您可能需要先将图形分解为连接的组件.来自维基百科的算法描述:
由John Hopcroft和Robert Tarjan(1973)[1]引起的用于计算连通无向图中的双连通分量的经典序列算法在线性时间内运行,并且基于深度优先搜索.该算法也概述为算法导论(第2版和第3版)的问题22-2.我们的想法是在保持以下信息的同时运行深度优先搜索:深度优先搜索树中的每个顶点的深度(一旦被访问),并且对于每个顶点v,所有后代的邻居的最低深度在深度优先搜索树中的v,称为低点.在深度优先搜索期间,深度是标准的.v的低点可以在访问v的所有后代之后计算(即,在v从深度优先搜索堆栈中弹出之前)作为v的深度的最小值,v的所有邻居的深度(除了深度优先搜索树中的v的父级和深度优先搜索树中的v的所有子级的低点.关键的事实是,当且仅当存在v的子y使得低点(y)≥深度(v)时,非根顶点v是将两个双连通分量分开的切割顶点(或铰接点).一旦从v的每个子节点返回深度优先搜索(即,在v从深度优先搜索堆栈中弹出之前),就可以测试该属性,并且如果为真,则v将图形分成不同的双连通组件.这可以通过计算每个这样的y中的一个双连通分量来表示(包含y的子组件将包含y的子树,加上v),然后从树中擦除y的子树.根顶点必须单独处理:当且仅当它至少有两个孩子时,它才是一个切割顶点.因此,只需从根(包括根)的每个子子树中构建一个组件就足够了.
可以在http://www.cs.umd.edu/class/fall2005/cmsc451/biconcomps.pdf找到一个好的伪代码实现.