[点连通度与边连通度]
在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。
类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。一个图的边连通度的定义为，最小割边集合中的边数。
[双连通图、割点与桥]
如果一个无向连通图的点连通度大于1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulation point)。
如果一个无向连通图的边连通度大于1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边(articulation edge)。
可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。
[双连通分支]
在图G的所有子图G’中，如果G’是双连通的，则称G’为双连通子图。如果一个双连通子图G’它不是任何一个双连通子图的真子集，则G’为极大双连通子图。双连通分支(biconnected component)，或重连通分支，就是图的极大双连通子图。特殊的，点双连通分支又叫做块。
[求割点与桥]
该算法是R.Tarjan发明的。对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点。根据定义，则有：
Low(u)=Min
{
DFS(u)
DFS(v) (u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点
Low(v) (u,v)为树枝边(父子边)
}
一个顶点u是割点，当且仅当满足(1)或(2)
(1) u为树根，且u有多于一个子树。
(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)。
一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。
[求双连通分支]
下面要分开讨论点双连通分支与边双连通分支的求法。
对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。
对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。
[构造双连通图]
一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。
统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
[图的双连通性问题例题]
备用交换机
求图的割点，直接输出。
pku 3177(3352) Redundant Paths
求桥，收缩边双连通子图，构造边双连通图。
POI 1999 仓库管理员 Store-keeper
求点双连通子图。
BYVoid 原创讲解，转载请注明。
四月 10th, 2009 at 17:44:34
[...] 这几天学了图的一些概念性的东西，有什么是路，什么是迹，什么是边的双连通分量，什么是点的双连通分量，等等这些概念，又回顾了一遍，详见http://www.byvoid.com/blog/biconnect/，在这里写的很清楚了。 [...]
四月 15th, 2009 at 07:58:56
[...] 求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。 [...]
“(1) u为树根，且u有多于一个子树。”这个好像有问题吧。。
[回复]
BYVoid 回复:
六月 1st, 2009 at 11:30:42
我觉得没有问题。无向图DFS生成树没有横叉边，不同子树一定属于不同点双连通分量
[回复]
BYVoid 回复:
六月 1st, 2009 at 12:41:28
这里的“子树”是无向图DFS生成树
[回复]
A discovery is said to be an accident meeting a prepared mind.
[回复]
Orz……来学习了。
[回复]
四月 6th, 2010 at 14:49:38
[...] 【求桥和双连通分量】pku3352&&pku3177 概念连接http://www.byvoid.com/blog/biconnect/ [...]
四月 14th, 2010 at 21:42:33
[...] 首先，我们应该学习一些基本概念和算法，参见byvoid神牛的：http://www.byvoid.com/blog/biconnect/。看完以后，直接做就是了。 poj 3352 Road [...]
四月 16th, 2010 at 11:02:50
[...] 2. 求出图中所有的点双连通分量。对于求图中的双连通分量，还是参考byvoid牛的：图的割点、桥与双连通分支。其中，byvoid牛写到“每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中”。在我的实现中，由于只需要知道每个双连通分量的点集，所以只记录了树枝边。 [...]
五月 2nd, 2010 at 11:19:38
[...] tarjan(u) { DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (v is not visted) // 如果节点v未被访问过 tarjan(v) // 继续向下找 Low[u] = min(Low[u], Low[v]) else if (v in S) // 如果节点u还在栈内 Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 repeat v = S.pop // 将v退栈，为该强连通分量中一个顶点 print v until (u== v) } 接下来是对算法流程的演示。 从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6} 为一个强连通分量。 返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。 返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是 横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。 继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现 DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。 至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。 可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为 O(N+M)。 求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是 O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。 但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。 在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量 (割点、桥)的Tarjan算法也有着很深的联系。 学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组 合理解。 求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的 Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。 [...]
看上去求BCC和求SCC的Low和Lowlink很相似,感觉一样的..到底是什么本质的不同呢?是一个是无向图一个是有向图的区别吗.
找BCC的代码应该和SCC的一样?
[回复]