如何输出无向图的所有双连通分量？
给定一个一般的无向图，如何在O(n+m)时间内打印出图的所有双连通分量？我知道Tarjan的算法，用于输出无向图的所有连接点，但我发现很难扩展该算法来打印双连接的组件。我试着搜索google，但我得到的所有结果都不能用于我的测试用例，因为它们错过了算法的边缘情况。
编辑：我已经成功地实现了Niklas提供的这个链接中描述的算法。现在我有一个不同的问题，我如何找出一个不含边的无向图的子图，如果删除它，子图就会断开连接。请帮我解决这个交替的问题。
共有1个答案
这是一个经典的线性时间算法问题。不过，您可能需要首先将图分解为连接的组件。来自维基百科的算法描述：
可以在http://www.cs.umd.edu/class/fall2005/cmsc451/biconcomps.pdf找到一个很好的伪代码实现。
-
我想在无向图中找到一个强连通分量，即如果我从一个节点开始，那么我将回到节点，并且每个边都被精确地访问一次。 对于有向图，可以用Tarjan算法求强连通分量，但是对于无向图，该怎么办。
-
根据CLRS第3版的定义，单连通有向图是指每对顶点(u，v)至多有一条唯一的路从u->v来的图。现在我读过的大多数答案都说，我们从图中的每个顶点运行DFS，如果在任何情况下我们找到一条交叉边或一条前向边，那么图就不是单连通的。我可以理解前向边的概念，但是在这个图上运行这个algo 1-->2<--3将给出一个结果：它不是单连通的，而这个图是单连通的。我们有一个从3->2或1->2的交叉边，这取决于
-
设，一个无向连通图，完全没有桥。描述了一种引导边的算法，使得新图是一个SCC。 我建议的算法 所以我们从任意顶点运行DFS。我们注意到，由于它是一个无向图，所以只有树边和后边（对吗？）。我们相应地连接边（一个树边将被引导为“向下”，一个后边将被引导为“向上”）。 谢谢
-
我正在研究一个优化问题，需要列出一个无向图的所有可能割集。具体来说，我感兴趣的是在两个顶点子集中找到所有断开图的边子集。 详细地： 在无向图G（V，E）中，V是顶点集，E是边集。割形成两个顶点子集a和B，这样： A联合B=V 和 A交叉点B=空集 A和B建立C（E的子集），使得C中的每条边连接两个顶点，一个在A中，一个在B中。我感兴趣的是找到所有可能的子集C，这样：对于每一个C，它是一个图的割，没
-
我在NetworkX中有一个有向无环简单图。 现在，对于每个边，该边都有一个“源”和一个“目标”。如果除了这个边之外，还有一条从“源”到“目标”的路径，那么我想删除这个边。 null > 节点为： 边缘是：