不得不佩服Tarjan，果然是計(jì)算機(jī)領(lǐng)域的牛人
求無(wú)向圖割點(diǎn)的算法其實(shí)比較容易理解，《算法導(dǎo)論》上思考題22-2有關(guān)于割點(diǎn)的討論，其中有證明題：
1、如果對(duì)于無(wú)向連通圖的DFS得來(lái)的生成樹(shù)的根T是割點(diǎn)，當(dāng)且僅當(dāng)T至少有兩個(gè)子女；
2、如果對(duì)于無(wú)向連通圖的DFS得來(lái)的生成樹(shù)的非根V是割點(diǎn)，當(dāng)且僅當(dāng)在生成樹(shù)中V有一個(gè)孩子節(jié)點(diǎn)S，使得不存在從S或S的任何后裔節(jié)點(diǎn)指向V的某個(gè)真祖先頂點(diǎn)的反向邊；
其實(shí)粗略證明并不難：
證明1：1）若T是割點(diǎn)，假設(shè)T僅有一個(gè)孩子節(jié)點(diǎn)t，則當(dāng)去掉T節(jié)點(diǎn)之后，原生成樹(shù)仍然為一顆樹(shù)，根節(jié)點(diǎn)為t，可知去掉T之后的圖仍然連通，與割點(diǎn)定義矛盾，因此如果T是割點(diǎn)，則T至少有兩個(gè)孩子節(jié)點(diǎn)成立；2）若T有至少兩個(gè)子女，則根據(jù)生成樹(shù)由DFS得到可知，在原圖中根節(jié)點(diǎn)的兩個(gè)子樹(shù)之間不存在連接邊，因此當(dāng)去掉根節(jié)點(diǎn)T后，兩顆子樹(shù)不能通過(guò)增加邊形成一棵新的生成樹(shù)，成為兩棵獨(dú)立的生成樹(shù)，因此可知原圖不在連通，所以由割點(diǎn)定義知T為割點(diǎn)；證畢。
證明2：1）若非根V是割點(diǎn)，假設(shè)生成樹(shù)中V的所有孩子節(jié)點(diǎn)Si，使得任意Si及其Si的后裔節(jié)點(diǎn)都存在指向V的某個(gè)真祖先頂點(diǎn)的反向邊，那么，當(dāng)去掉節(jié)點(diǎn)V之后，生成樹(shù)中V節(jié)點(diǎn)的子樹(shù)可以通過(guò)連接反向邊形成一棵新的生成樹(shù)，則原圖在去掉V節(jié)點(diǎn)后仍然連通，與V是割點(diǎn)矛盾，因此若對(duì)于無(wú)向連通圖的DFS得來(lái)的生成樹(shù)的非根V是割點(diǎn)，則在生成樹(shù)中V有一個(gè)孩子節(jié)點(diǎn)S，使得不存在從S或S的任何后裔節(jié)點(diǎn)指向V的某個(gè)真祖先頂點(diǎn)的反向邊成立；2）若在生成樹(shù)中V有一個(gè)孩子節(jié)點(diǎn)S，使得不存在從S或S的任何后裔節(jié)點(diǎn)指向V的某個(gè)真祖先頂點(diǎn)的反向邊，則生成樹(shù)中V的一孩子節(jié)點(diǎn)S為根的子樹(shù)，在去掉V節(jié)點(diǎn)之后不能通過(guò)增加指向真祖先頂點(diǎn)的方向邊形成一棵去掉V節(jié)點(diǎn)后的新圖的生成樹(shù)，則原圖在去掉V節(jié)點(diǎn)后成為不連通的圖，則V是割點(diǎn)，成立；證畢。
有了上面的理論保證，則求割點(diǎn)的算法就不難了：
1）對(duì)連通圖進(jìn)行DFS，遍歷過(guò)程中記錄所有節(jié)點(diǎn)的深度值depth，并且對(duì)節(jié)點(diǎn)Vi記錄下Vi自身及其Vi所有子孫節(jié)點(diǎn)見(jiàn)過(guò)的深度最淺的深度值low（不包括節(jié)點(diǎn)本身的父節(jié)點(diǎn)）；
2）如果Vi節(jié)點(diǎn)不為根節(jié)點(diǎn)，則如果Vi存在某個(gè)兒子節(jié)點(diǎn)，其見(jiàn)過(guò)的深度最淺的深度值要大于節(jié)點(diǎn)Vi的深度值，則Vi為割點(diǎn)；
3）如果Vi為根節(jié)點(diǎn)，則如果Vi有兩個(gè)及其以上的子女，則Vi為割點(diǎn)；
代碼如下：
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;//父親節(jié)點(diǎn)
32 node[i].depth = -1;//深度
33 node[i].low = -1;//子孫節(jié)點(diǎn)見(jiàn)到的depth最小的節(jié)點(diǎn)號(hào)
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函數(shù)，它有三個(gè)參數(shù)，代表當(dāng)前遍歷的節(jié)點(diǎn)，該節(jié)點(diǎn)的父親節(jié)點(diǎn)，節(jié)點(diǎn)的深度值。其中每個(gè)節(jié)點(diǎn)都有一個(gè)顏色值來(lái)表示當(dāng)前遍歷的狀態(tài)，如果節(jié)點(diǎn)還未被遍歷，則為WHITE，如果該節(jié)點(diǎn)已經(jīng)被訪問(wèn)，但是正在遍歷其孩子節(jié)點(diǎn)，則該節(jié)點(diǎn)為GREY，如果該節(jié)點(diǎn)及其所有孩子節(jié)點(diǎn)均被遍歷，則該節(jié)點(diǎn)被標(biāo)記為BLACK；
求無(wú)向連通圖的割邊算法與割點(diǎn)很類(lèi)似，割點(diǎn)是求孩子節(jié)點(diǎn)的low值是否大于等于該節(jié)點(diǎn)的depth，如果low[child] >= depth[V]，則該點(diǎn)V為割點(diǎn)，如果low[child] > depth[v]，則v-child連接的這條邊則為割邊。
posted on 2012-08-18 23:53
myjfm 閱讀(2881)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
算法基礎(chǔ)