强连通分支（精选）.ppt

强连通分支、桥和割点
思想:
做一遍DFS,用dfn[i]表示编号为i的节点在DFS过程中的访问序号(也可以叫做开始时间)用low[i]表示i节点及其下方节点所能到达的开始时间最早的节点的开始时间。初始时dfn[i]=low[i]
在DFS过程中会形成一搜索树。在搜索树上越上层的节点,显然dfn的值就越小。
如果发现某节点有边连到搜索树中自己的祖先节点,则更新其low 值。
有向图强连通分支的Tarjan算法
如果一个节点的low 值小于dfn值,那么就说明它或其子孙节点有边连到自己上方的节点
如果一个节点的low值等于dfn值,则说明其下方的节点不能走到其上方的节点,那么该节点u就是一个强连通分量在DFS搜索树中的根。
但是u的子孙节点未必就和u处于同一个强连通分量,怎么办?用栈解决.
有向图强连通分支的Tarjan算法
有向图强连通分支的Tarjan算法
void Tarjan(u) {
d[u]=low[u]=++index
(u)
for each (u, v) in E {
if (v is not visted) {
tarjan(v)
low[u] = min(low[u], low[v])
}
else if (v in stack) {
low[u] = min(low[u], d[v])
}
}
if (d[u] == low[u]) { //u是一个强连通分量的根
repeat
v =
print v
until (u== v)
} //退栈,把整个强连通分量都弹出来
} //复杂度是O(n)的
无向连通图求割点和桥
无向连通图中,如果删除某点后,图变成不连通,则称该点为割点。
无向连通图中,如果删除某边后,图变成不连通,则称该边为桥。
求桥和割点的Tarjan算法
思路和有向图求强连通分量类似
一个顶点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过程中形成的搜索树
求桥和割点和桥的Tarjan算法
Tarjan(u) {
d[u]=low[u]=++index
for each (u, v) in E {
if (v is not visted)
tarjan(v)
low[u] = min(low[u], low[v])
d[u]<low[v] (u, v) 是桥
}
else {
if( u 不是 v的父节点)
low[u] = min(low[u], d[v])
}
}
if (u is root)
u 是割点<=> u 有至少两个子节点
else
u 是割点<=> u 有一个子节点v,满足d[u]<= low[v]
}
Tarjan’s algorithm
注意,这里的反向边(连接到dfs搜索树祖先的边)不考虑反向连接父亲的那条边
另外,low[u]定义为u或者u的子树中能够通过非父子边追溯到的最早的节点的DFS开始时间
Tarjan’s algorithm
也可以先用Tajan()进行dfs算出所有点的low和dfn值,并记录dfs过程中每个点的父节点,然后再把所有点看一遍,看其low和dfn,以找出割点和桥。
找桥的时候,要注意看有没有重边。有重边,则不是桥。
求无向图连通图点双连通分支(不包含割点的极大连通子图):
对于点双连通分支,实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈,存储当前双连通分支,在搜索图时,每找到一条树枝边或反向边,就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v),说明u是一个割点,同时把边从栈顶一个个取出,直到遇到了边(u,v),取出的这些边与其关联的点,组成一个点双连通分支。割点可以属于多个点双连通分支,其余点和每条边只属于且属于一个点双连通分支。