首页 > 代码库 > 《数据结构与算法分析: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 }