图论(1)：使用tarjan算法寻找无向连通图中的割点与桥

图论 12 分钟 读完 (约 1837 字)

Tarjan算法是图论中常用的算法之一，本篇作为图论的第一篇，首先从无向图着手，记录如何使用tarjan算法解决寻找无向连通图中的割点与桥的问题。

1 割点与桥

割点与桥存在于无向图中。

1.1 定义

  • 割点：无向连通图中，去掉一个顶点及和它相邻的所有边，图中的连通分量数增加，则该顶点称为割点。
  • 桥：无向连通图中，去掉一条边，图中的连通分量数增加，则这条边，称为桥或者割边。

1.2 割点与桥的关系

  • 有割点不一定有桥
  • 桥一定是割点依附的边

2 暴力解法

关于如何解决寻找无向图中的割点与桥的问题，我们可以从割点与桥的定义出发，从图中每次去掉一个顶点和它相邻的所有边，然后进行DFS遍历，如果连通分量增加了，那么去掉的顶点就是割点（桥同理）。但这样我们需要对图上的每个顶点（边）进行一次上述操作，显然时间复杂度过于高了，那有没有只进行一次DFS遍历的解决方案呢？这就要引出本文的主题-Tarjan算法了。

3 Tarjan算法原理

我们首先假设在DFS中从顶点U访问到了顶点V，即V是U的孩子节点，在顶点U访问之前访问过的节点就是U的祖先节点。显然，如果顶点U的全部孩子节点都可以不通过父亲节点U访问到U的祖先节点，那么就说明当我们去掉顶点U时，无向图的连通性没有发生改变，因此U就不是割点；相反的，如果U至少存在一个孩子节点只能通过U才能访问到U的祖先节点，那么U为割点。

3.1 具体实现

除了要借助DFS外，我们还需要定义两个数组，dfn[n]和low[n], 前者代表深度优先遍历的顶点顺序（时间戳），后者代表当前顶点不通过其父亲节点可以访问到的祖先节点的最小时间戳。

当我们从顶点U深度优先遍历到顶点V时（V不是U的父亲节点）：

  • 如果V没有被访问过，则说明V是U的孩子节点，继续对V进行DFS。注意返回到U时，需要更改U的low值，即 low[U] = min(low[U], low[V])。
  • 如果V已经被访问过，则说明V是U的祖先节点，即我们找到了可以不通过U的父亲节点而访问到其祖先节点的路径，更新low[U] = min(low[U], dfn[V])

3.2 寻找割点

判断割点集有一个特殊顶点需要额外进行判断，即根节点，因为通过tarjan算法我们需要借助祖先节点，但是根节点并没有祖先节点，那我们如何对根节点是否为割点进行判断呢？其实也不难看出，如果我们从根节点进行DFS遍历，如果一次DFS就能遍历完整个无向图上的所有节点，那根节点就不是割点，反之，则根节点是割点。

对于除root节点外的其他节点，我们就可以通过tarjan算法进行判断了，当U节点至少存在一个孩子节点V，使得 low[V] >= dfn[U] 时，U即为一个割点。

  • 代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // time = 1;
    // vector<vector<int>> graph(n);
    // int dfn[n], low[n];
    // vector<int> points;
    void tarjan(int x, int parent, int root) {
        // 第一次遍历到当前 x 节点
        dfn[x] = low[x] = time++;
        // children用于记录 x 下有几个连通图
        int children = 0;
        for (const int & y : graph[x]) {
        	// y 为父亲节点，跳过
            if (y == parent) continue;
            // y 未访问过
            else if (dfn[y] == 0) {
                ++children;
                tarjan(y, x, root);
                low[x] = min(low[x], low[y]);
                // 注意判断条件为大于等于
                if (x != root && low[y] >= dfn[x]) points.push_back(x);
            }
            // y 是 x 的祖先节点
            else low[x] = min(low[x], dfn[y]);
        }
        // x 是根节点，且 x 无法通过一次DFS遍历访问完所有节点
        if (x == root && children > 1) points.push_back(root);
    }

3.3 寻找桥

桥的判断条件与割点类似，只不过不需要单独像割点一样去判断根节点，因为判断桥是判断的是图中的边啦！但判断条件改为 low[V] > dfn[U]。

  • 代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // time = 1;
    // vector<vector<int>> graph(n);
    // int dfn[n], low[n];
    // vector<int> ans;
    void tarjan(int x, int parent) {
        dfn[x] = low[x] = time++;
        for (const int &y : graph[x]) {
            if (y == parent) continue;
            else if (dfn[y] == 0) {
                tarjan(y, x);
                low[x] = min(low[x], low[y]);
                // 注意判断条件
                if (low[y] > dfn[x]) ans.push_back({x, y});
            }
            else low[x] = min(low[x], dfn[y]);
        }
    }

4 Leetcode题目实例

4.1 1192 查找集群内的「关键连接」

题目给定的输入是一个连通的无向图，输出即为无向连通图的所有桥。对于这道题，我们完全可以套用tarjan算法的模板，找出图中所有的桥即可。

  • 代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
    private:
        vector<vector<int>> ans;
        vector<int> dfn;
        vector<int> low;
        vector<vector<int>> graph;
        int time = 1;
    public:
        vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
            graph.resize(n);
            for (const auto & e: connections) {
                graph[e[0]].push_back(e[1]);
                graph[e[1]].push_back(e[0]);
            }
            dfn.resize(n, 0);
            low.resize(n, 0);
            tarjan(1, -1);
            return ans;
        }
        void tarjan(int x, int parent) {
            dfn[x] = low[x] = time++;
            for (const int &y : graph[x]) {
                if (y == parent) continue;
                else if (dfn[y] == 0) {
                    tarjan(y, x);
                    low[x] = min(low[x], low[y]);
                    if (low[y] > dfn[x]) ans.push_back({x, y});
                }
                else low[x] = min(low[x], dfn[y]);
            }
        }
    };

4.2 1568 使陆地分离的最少天数

这道题相对于前一道上升了些许难度，但实质也可以看作一道寻找割点的题目，这里我们用到了并查集和tarjan算法。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class UnionFind {
private:
    vector<int> parent;
    int n_size;
public:
    UnionFind(int _n): n_size(_n) {
        parent.resize(_n+1);
        for (int i = 1; i <= _n; ++i) parent[i] = i;
    }
    int find(int x) {
        return x == parent[x] ? parent[x] : parent[x] = find(parent[x]);
    }
    void merge(int u, int v) {
        if (find(u) == find(v)) return;
        parent[find(u)] = find(v);
        --n_size;
    }
    int get_nsize() {
        return n_size;
    }
};

class Solution {
private:
    vector<int> directions = {-1, 0, 1, 0, -1};
    vector<vector<int>> graph;
    vector<int> dfn;
    vector<int> low;
    int time = 1;
    vector<int> points;

public:
    int minDays(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        unordered_map<int, int> relabel;
        int index = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    relabel[i*n+j] = index++;
                }
            }
        }
        int cnt = relabel.size();
        if (cnt == 0) return 0;
        else if (cnt == 1) return 1;
        else {
            UnionFind uf = UnionFind(cnt);
            graph.resize(cnt);
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == 1) {
                        for (int k = 0; k < 4; ++k) {
                            int ni = i + directions[k], nj = j + directions[k+1];
                            if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                                graph[relabel[i*n+j]].push_back(relabel[ni*n+nj]);
                                uf.merge(relabel[i*n+j], relabel[ni*n+nj]);
                            }
                        }
                    }
                }
            }
            int n_size = uf.get_nsize();
            if (n_size > 1) return 0;
            dfn.resize(cnt, 0), low.resize(cnt, 0);
            tarjan(0, -1, 0);
            if (points.size() > 0) return 1;
            else return 2;
            return 0;
        }
    }

    void tarjan(int x, int parent, int root) {
        dfn[x] = low[x] = time++;
        int children = 0;
        for (const int & y : graph[x]) {
            if (y == parent) continue;
            else if (dfn[y] == 0) {
                ++children;
                tarjan(y, x, root);
                low[x] = min(low[x], low[y]);
                if (x != root && low[y] >= dfn[x]) points.push_back(x);
            }
            else low[x] = min(low[x], dfn[y]);
        }
        if (x == root && children > 1) points.push_back(root);
    }
};

#Algorithm
LeetCode买卖股票问题合集 DeBERTa 论文解读
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×