不得不佩服Tarjan，果然是计算机领域的牛人
求无向图割点的算法其实比较容易理解，《算法导论》上思考题22-2有关于割点的讨论，其中有证明题：
1、如果对于无向连通图的DFS得来的生成树的根T是割点，当且仅当T至少有两个子女；
2、如果对于无向连通图的DFS得来的生成树的非根V是割点，当且仅当在生成树中V有一个孩子节点S，使得不存在从S或S的任何后裔节点指向V的某个真祖先顶点的反向边；
其实粗略证明并不难：
证明1：1）若T是割点，假设T仅有一个孩子节点t，则当去掉T节点之后，原生成树仍然为一颗树，根节点为t，可知去掉T之后的图仍然连通，与割点定义矛盾，因此如果T是割点，则T至少有两个孩子节点成立；2）若T有至少两个子女，则根据生成树由DFS得到可知，在原图中根节点的两个子树之间不存在连接边，因此当去掉根节点T后，两颗子树不能通过增加边形成一棵新的生成树，成为两棵独立的生成树，因此可知原图不在连通，所以由割点定义知T为割点；证毕。
证明2：1）若非根V是割点，假设生成树中V的所有孩子节点Si，使得任意Si及其Si的后裔节点都存在指向V的某个真祖先顶点的反向边，那么，当去掉节点V之后，生成树中V节点的子树可以通过连接反向边形成一棵新的生成树，则原图在去掉V节点后仍然连通，与V是割点矛盾，因此若对于无向连通图的DFS得来的生成树的非根V是割点，则在生成树中V有一个孩子节点S，使得不存在从S或S的任何后裔节点指向V的某个真祖先顶点的反向边成立；2）若在生成树中V有一个孩子节点S，使得不存在从S或S的任何后裔节点指向V的某个真祖先顶点的反向边，则生成树中V的一孩子节点S为根的子树，在去掉V节点之后不能通过增加指向真祖先顶点的方向边形成一棵去掉V节点后的新图的生成树，则原图在去掉V节点后成为不连通的图，则V是割点，成立；证毕。
有了上面的理论保证，则求割点的算法就不难了：
1）对连通图进行DFS，遍历过程中记录所有节点的深度值depth，并且对节点Vi记录下Vi自身及其Vi所有子孙节点见过的深度最浅的深度值low（不包括节点本身的父节点）；
2）如果Vi节点不为根节点，则如果Vi存在某个儿子节点，其见过的深度最浅的深度值要大于节点Vi的深度值，则Vi为割点；
3）如果Vi为根节点，则如果Vi有两个及其以上的子女，则Vi为割点；
代码如下：
1 #include <cstdio>
2 #include <vector>
3
4 #define IntVector std::vector<int>
5 #define min(x, y) ((x) > (y) ? (y) : (x))
6 #define MAXN 105
7 #define ROOT 1
8 #define WHITE 0
9 #define GREY 1
10 #define BLACK 2
11
12 struct Node {
13 IntVector nbs;
14 int parent;
15 int depth;
16 int low;
17 int color;
18 };
19
20 Node node[MAXN];
21 int flag[MAXN];
22 int Nnode;
23 int CPCount;
24 int ChildrenOfRoot;
25
26 void Init() {
27 int i;
28 for (i = 0; i < MAXN; ++i) {
29 flag[i] = 0;
30 node[i].nbs.clear();
31 node[i].parent = -1;//父亲节点
32 node[i].depth = -1;//深度
33 node[i].low = -1;//子孙节点见到的depth最小的节点号
34 node[i].color = WHITE;
35 }
36 CPCount = 0;
37 ChildrenOfRoot = 0;
38 }
39
40 void Output() {
41 printf("%d\n", CPCount);
42 }
43
44 int TarjanDFS(int CurNode, int Parent, int Depth) {
45 int i;
46 node[CurNode].parent = Parent;
47 node[CurNode].color = GREY;
48 node[CurNode].depth = node[CurNode].low = Depth;
49 for (i = 0; i < node[CurNode].nbs.size(); ++i) {
50 if (node[CurNode].nbs[i] == Parent) {
51 continue;
52 }
53 if (node[node[CurNode].nbs[i]].color == GREY) {
54 node[CurNode].low = min(node[node[CurNode].nbs[i]].depth,
55 node[CurNode].low);
56 } else if (node[node[CurNode].nbs[i]].color == WHITE) {
57 TarjanDFS(node[CurNode].nbs[i], CurNode, Depth + 1);
58 node[CurNode].low = min(node[CurNode].low,
59 node[node[CurNode].nbs[i]].low);
60 if (CurNode == ROOT) {
61 ChildrenOfRoot++;
62 }
63 if (CurNode != ROOT &&
64 node[CurNode].depth <= node[node[CurNode].nbs[i]].low) {
65 flag[CurNode] = 1;
66 }
67 }
68 }
69 node[CurNode].color = BLACK;
70 }
71
72 void FindCutPoint() {
73 int i;
74 TarjanDFS(1, 0, 1);
75 for (i = 2; i <= Nnode; ++i) {
76 if (flag[i] == 1) {
77 CPCount++;
78 }
79 }
80 if (ChildrenOfRoot > 1) {
81 CPCount++;
82 }
83 }
84
85 void Run() {
86 int tmp1, tmp2;
87 char ch;
88 while (scanf("%d", &Nnode) && Nnode != 0) {
89 Init();
90 while (scanf("%d", &tmp1) && tmp1 != 0) {
91 while (scanf("%d%c", &tmp2, &ch)) {
92 node[tmp1].nbs.push_back(tmp2);
93 node[tmp2].nbs.push_back(tmp1);
94 if (ch == '\n') {
95 break;
96 }
97 }
98 }
99 FindCutPoint();
100 Output();
101 }
102 }
103
104 int main() {
105 Run();
106 return 0;
107 }
108
核心代码便是TarjanDFS函数，它有三个参数，代表当前遍历的节点，该节点的父亲节点，节点的深度值。其中每个节点都有一个颜色值来表示当前遍历的状态，如果节点还未被遍历，则为WHITE，如果该节点已经被访问，但是正在遍历其孩子节点，则该节点为GREY，如果该节点及其所有孩子节点均被遍历，则该节点被标记为BLACK；
求无向连通图的割边算法与割点很类似，割点是求孩子节点的low值是否大于等于该节点的depth，如果low[child] >= depth[V]，则该点V为割点，如果low[child] > depth[v]，则v-child连接的这条边则为割边。
posted on 2012-08-18 23:53
myjfm 阅读(2793)
评论(0) 编辑 收藏 引用 所属分类:
算法基础