《数据结构与算法分析：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 }