该算法是R.Tarjan发明的。过程与求强连通图的类似。wiki

求割点

基本概念

割点:无向图连通分量中,如果删除其中某点以及与该点相连的边后,连通分量变成不连通,则称该点为割点。

实现

在Tarjan算法的过程中,当前结点u是割点的条件为:

  1. u 为在 dfs 上的根结点, 即 u 的 father 为 nil , 此时需要满足 u 的子结点数量要大于 1 且其中至少有一个子结点满足 v.index==v.lowlink
  2. u 为非根结点, u.index == u.lowlink

注意:度为1(不考虑重边的情况下)的结点虽然满足以上条件,但是不是割点。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
algorithm tarjan_cutpoint is
input: # 图 G = (V, E)
output: # 以所在的强连通分量划分的顶点集
for each u in V do
u.flag = 0 # 0 未找到, 1 已找到, 2 访问结束

index := 0
for each u in V do
if (u.flag == 0)
findcutpoints(u, nil, index)
end if

function findcutpoints(u, father, index)
# 将未使用的最小index值作为结点u的index
u.index := index
u.lowlink := index
index := index + 1

childs = 0
# index 与 lowlink 相等的点的数量
validchilds = 0
# 考虑u的后继结点
for each (u, v) in E do
if (v.flag == 0) then
# 后继结点v未访问,递归调用
findcutpoints(v, u, index)
u.lowlink := min(u.lowlink, v.lowlink)
childs++;
if (v.lowlink == v.index)
validchilds++;
end if
else
# v已经找到或已访问
if(v != father)
u.lowlink := min(u.lowlink, v.index)
end if
end if

if (father == nil && childs > 1 && validchilds > 0) then
# u为根结点
u is cut point
else if (father != nil && u.lowlink == u.index && childs != 0) then
# u不为根结点, childs == 0 时, 该点度为1
u is cut point
end if

u.flag = 2
end function

求桥

基本概念

桥:存在于无向图连通分量中的这样的一条边,如果去掉这一条边,连通分量不再连通,这样的一条边称为桥。

实现

桥的求法其实也是类似的,它的求法可以看成是割顶的一种特殊情况,当结点 u 的子结点 v 的后代通过反向边只能连回 v ,那么删除这条边 (u, v) 就可以使得图G非连通了。

注意:找桥的时候,看看有没有重边,有重边的边一定不是桥,也要避免误判。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
algorithm tarjan_bridges is
input: # 图 G = (V, E)
output: # 以所在的强连通分量划分的顶点集
for each u in V do
u.flag = 0 # 0 未找到, 1 已找到, 2 访问结束

index := 0
for each u in V do
if (u.flag == 0)
findbridges(u, nil, index)
end if

function findbridges(u, father, index)
# 将未使用的最小index值作为结点u的index
u.index := index
u.lowlink := index
index := index + 1

# 与father相连的边的数量
u.fatheredges = 0
# 考虑u的后继结点
for each (u, v) in E do
if (v.flag == 0) then
# 后继结点v未访问,递归调用
findbridges(v, u, index)
u.lowlink := min(u.lowlink, v.lowlink)

if (v.lowlink == v.index && v.fatheredges < 2)
# v为割点或则是度为1的点, 且v与u无重边
(u, v) is bridge
end if
else
# v已经找到或已访问
if(v != father)
u.lowlink := min(u.lowlink, v.index)
else
u.fatheredges++
end if
end if

u.flag = 2
end function

References