首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第九章“图论”——割点
《数据结构与算法分析：C语言描述》复习——第九章“图论”——割点
2014.07.04 23:57
简介：
这本教材中提到了一个概念，叫关节点（articulation point）。如果从某个无向图里去掉某个顶点以及这个顶点所有的边，如果此时图中连通分量的个数增加了，那么定义这个顶点为“关节点”。更通俗地解释，可以说如果拿走这个顶点，这幅图就破成了好几块，因此这个点好比“关节”，没有了关节整个结构也就破坏掉了。
后来上网搜了资料后，我才知道原来这就是割点。
描述：
解决这个问题的思路有以下几个线索：
1. 选取一个节点执行深度优先搜索，逐渐生成一棵树。初始的那个顶点就是根节点。
2. 如果根节点有至少2棵子树，那么根节点是割点（这个容易理解，如果拿走了根节点，就会出现多棵树）。
3. 对于其他顶点v，如果v的所有子节点（不一定是直接相连的子节点）都不存在指向v的祖先的回路，那么v是割点（这个不太好理解，其实意思是说拿走了v以后，下面的子节点就无法连接到v以上的祖先节点了，这样图就断开了）。
根据这三点思路，可以写出以下代码。
实现：
1 // My implementation for cut vertex detection on undirected graph. 2 #include <algorithm> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 void findCutVertex(const vector<vector<bool> > &graph, int idx, const int n, 8 int &counter, vector<int> &num, vector<int> &low, vector<int> &parent, 9 vector<bool> &result) 10 { 11 int i; 12 13 low[idx] = num[idx] = counter++; 14 for (i = 0; i < n; ++i) { 15 if (!graph[idx][i]) { 16 continue; 17 } 18 19 if (num[i] < 0) { 20 // Unvisited vertex 21 parent[i] = idx; 22 findCutVertex(graph, i, n, counter, num, low, parent, result); 23 if (low[i] >= num[idx]) { 24 result[idx] = true; 25 } 26 low[idx] = min(low[idx], low[i]); 27 } else if (parent[idx] != i) { 28 // Visited vertex 29 low[idx] = min(low[idx], num[i]); 30 } 31 } 32 } 33 34 void cutVertexDetection(const vector<vector<bool> > &graph, 35 vector<bool> &is_cut_vertex) 36 { 37 // Cut vertex detection for undirected graph. 38 int n; 39 40 n = (int)graph.size(); 41 is_cut_vertex.resize(n, false); 42 43 if (n == 1) { 44 is_cut_vertex[0] = true; 45 return; 46 } 47 48 vector<int> parent; 49 vector<int> num; 50 vector<int> low; 51 int counter; 52 53 parent.resize(n, -1); 54 num.resize(n, -1); 55 low.resize(n, -1); 56 counter = 0; 57 findCutVertex(graph, 0, n, counter, num, low, parent, is_cut_vertex); 58 59 // The root node must be checked separately. 60 counter = 0; 61 for (int i = 1; i < n; ++i) { 62 if (parent[i] == 0) { 63 ++counter; 64 } 65 } 66 is_cut_vertex[0] = (counter > 1); 67 68 parent.clear(); 69 num.clear(); 70 low.clear(); 71 } 72 73 int main() 74 { 75 vector<vector<bool> > graph; 76 vector<bool> is_cut_vertex; 77 int n; 78 int nk; 79 int i, j; 80 int tmp; 81 82 while (cin >> n && n > 0) { 83 graph.resize(n); 84 for (i = 0; i < n; ++i) { 85 graph[i].resize(n, false); 86 } 87 88 for (i = 0; i < n; ++i) { 89 cin >> nk; 90 for (j = 0; j < nk; ++j) { 91 cin >> tmp; 92 graph[i][tmp] = graph[tmp][i] = true; 93 } 94 } 95 96 cutVertexDetection(graph, is_cut_vertex); 97 cout << "The following vertices are cut vertices:" << endl; 98 cout << ‘{‘; 99 for (i = 0; i < n; ++i) {100 if (is_cut_vertex[i]) {101 cout << i << ‘ ‘;102 }103 }104 cout << ‘}‘ << endl;105 106 for (i = 0; i < n; ++i) {107 graph[i].clear();108 }109 graph.clear();110 is_cut_vertex.clear();111 }112 113 return 0;114 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。