算法随笔图论问题:割点割边

割点

定义

割点的定义：如果一个点被删除之后会导致整个图不再是一个连通图，那么这个顶点就是这个图的割点。举例：

 上图中的点2就是一个割点，如果它被删除，则整个图被分为两个连通分量，不再是一个连通图。

求割点的方法

最直观容易想到的一种简单朴素的方法：

依次删除每一个顶点，然后用dfs或者bfs来检查图是否依然连通。如果删除某个顶点后，导致图不再连通，那么刚才删除的顶点就是割点。

这种方法的时间复杂度是O(N(N M))。显然不是一个高性能的算法。

考虑更高性能的算法：

考虑从根节点开始进行DFS遍历，遍历的同时记录每个节点的遍历顺序（又称为时间戳）到数组num。如下图：

圆圈中数字是顶点编号， 圆圈右上角的数表示这个顶点的“时间戳” 。

那么在遍历过程中如何判断割点？见下表：

那么该算法具体如何实现呢？

定义一个数组low来记录每个顶点在不经过父顶点时，能够回到的最小“时间戳”。

对于某个顶点u，如果存在至少一个顶点v（u的儿子），使得low[v]>=num[u]，即不能退回到祖先，顶多退回到顶点u，那么u点为割点。

示例代码（POJ1144）

1.  
   #include <iostream>
2.  
   #include <algorithm>
3.  
   #include <cstring>
4.  
   #include <vector>
5.  
   using namespace std;
6.  
   #define endl '\n'
7.  
   typedef long long ll;
8.  
   typedef unsigned long long ull;
9.  
   const int maxn = 1e2 10;
10.  
    const int INF = 0x3fffffff;
11.  
    const int mod = 1000000007;
12.  
    int num[maxn]; // 记录每个点的dfs遍历顺序
13.  
    int low[maxn]; // low[v]记录v和v的后代能连回到的祖先的num
14.  
    int dfn; // 记录进入递归的顺序（也称为时间戳）
15.  
    bool isCut[maxn]; // 标记割点
16.  
    vector<int> G[maxn];
17.  
     
18.  
    void dfs(int u, int fa) { // 当前节点u，u的父节点fa
19.  
    low[u] = num[u] = dfn; // 记录该点的遍历顺序，该点的low值初始等于num
20.  
    int child = 0; // 子树数目
21.  
    for (int i = 0; i < G[u].size(); i ) { // 处理u的所有子节点
22.  
    int v = G[u][i];
23.  
    if (!num[v]) { // v没访问过
24.  
    child ;
25.  
    dfs(v, u);
26.  
    low[u] = min(low[u], low[v]); // 用后代的返回值更新low值，从v以及v的后代可以回退到的祖先的num值
27.  
    if (low[v] >= num[u] && u != 1) { // 对于非根节点，u的直接子v或者v的后代没有回退到u的祖先的边，则u是割点
28.  
    isCut[u] = true;
29.  
    }
30.  
    } else if (num[v] < num[u] && v != fa) { // 处理回退边
31.  
    low[u] = min(low[u], num[v]);
32.  
    }
33.  
    }
34.  
    if (u == 1 && child >= 2) { // 对于根节点，有两棵以上不相连的子树，则根节点是割点
35.  
    isCut[1] = true;
36.  
    }
37.  
    }
38.  
     
39.  
    void solve() {
40.  
    int n, ans;
41.  
    while (cin >> n, n) {
42.  
    if (n == 0)
43.  
    break;
44.  
    memset(low, 0, sizeof low);
45.  
    memset(num, 0, sizeof num);
46.  
    dfn = 0;
47.  
    for (int i = 1; i <= n; i ) {
48.  
    G[i].clear();
49.  
    }
50.  
    int a, b;
51.  
    while (cin >> a, a) {
52.  
    while (cin.get() != '\n') {
53.  
    cin >> b;
54.  
    G[a].push_back(b);
55.  
    G[b].push_back(a);
56.  
    }
57.  
    }
58.  
    memset(isCut, 0, sizeof isCut);
59.  
    ans = 0;
60.  
    dfs(1, 1);
61.  
    for (int i = 1; i <= n; i ) {
62.  
    ans = isCut[i];
63.  
    }
64.  
    cout << ans << endl;
65.  
    }
66.  
    }
67.  
     
68.  
    int main() {
69.  
    ios::sync_with_stdio(false);
70.  
    cin.tie(0);
71.  
    cout.tie(0);
72.  
    cout << fixed;
73.  
    cout.precision(18);
74.  
     
75.  
    solve();
76.  
    return 0;
77.  
    }

割边

定义

如果在一个无向图中删除某条边后，图不再连通，那么这条边叫做割边（又称桥）。举例：

求割边的方法

只需将求割点的算法修改一个符号就可以。 只需将low[v]>=num[u]改为low[v]>num[u]。

这是为什么呢？

low[v]和num[u]相等则表示还可以回到父亲结点； 而low[v]>num[u]则表示连父亲都回不到了。倘若顶点v不能回到祖先，也没有另外的路能回到父亲，那么 u-v 这条边就是割边。

割边代码

……后边补上……

注：本文的部分内容和图片参考了 https://www.cnblogs.com/ljy-endl/p/11595161.html

这篇好文章是转载于：学新通技术网