不得不佩服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 閱讀(2919)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎