算法图算法

在无向图中判定环

字数统计: 3.4k字   |   阅读时长: 16分
, , ,

摘要: 无向图上的环的判定

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们系统梳理一下判定无向图中是否存在环的问题。首先介绍四种算法，分别为 BFS、DFS、并查集、拓扑排序，均为图上的主流算法，建议全都掌握。

然后我们看两个相关的问题，一个是给定一条边判断该边是否在环上，另一个是判定是否存在边数至少为 4 的环。

$1 判定：是否存在环(模板)

无向图中环判定：在 DFS 的过程中找到一个点，它不是 prev 点(DFS前驱)而又在此前遍历过，则形成环。

但注意如果是有向图，则访问到一个以前访问过的点并不代表形成环。参考 有向图的环。

1
bool has_cycle(const vector<vector<int>>& g);

算法1: dfs 染色

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
bool dfs(const vector<vector<int>>& g, int u, int prev, vector<bool>& visited)
{
    for(int v: g[u])
    {
        if(v == prev)
            continue;
        if(visited[v])
            return true;
        visited[v] = true;
        if(dfs(g, v, u, visited))
            return true;
    }
    return false;
}

bool has_cycle(const vector<vector<int>>& g)
{
    int n = g.size();
    vector<bool> visited(n, false);
    for(int i = 0; i < n; ++i)
    {
        if(visited[i]) continue;
        visited[i] = true;
        if(dfs(g, i, -1, visited))
            return true;
    }
    return false;
}

算法2: bfs 染色

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
struct State
{
    int node;
    int prev;
    State(int node, int prev):node(node),prev(prev){}
};

bool bfs(const vector<vector<int>>& g, vector<bool>& visited, int start)
{
    queue<State> q;
    q.push(State(start, -1));
    while(!q.empty())
    {
        State s = q.front();
        for(int son: g[s.node])
        {
            if(son == s.prev)
                continue;
            if(visited[son])
                return true; // 找到环
            visited[son] = true;
            q.push(State(son, s.node));
        }
    }
    return false;
}

bool has_cycle(const vector<vector<int>>& g)
{
    int n = g.size();
    vector<bool> visited(n, false);
    for(int i = 0; i < n; ++i)
    {
        if(visited[i])
            continue;
        visited[i] = true;
        if(bfs(g, visited, i))
            return true;
    }
    return false;
}

算法3: 并查集

Kruskal 算法中的一步。

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
class UnionFindSet
{
public:
    UnionFindSet(int N)
    {
        _father = vector<int>(N + 1, -1);
        _rank = vector<int>(N + 1, 1);
        for(int i = 0; i <= N; ++i)
            _father[i] = i;
    }

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);

        if(x == y) return;
        if(_rank[x] < _rank[y])
            _father[x] = y;
        else
            _father[y] = x;
        if(_rank[x] == _rank[y])
            ++_rank[x];
    }

private:
    vector<int> _father;
    vector<int> _rank;

    int _find(int x)
    {
        if(_father[x] == x) return x;
        return _father[x] = _find(_father[x]);
    }
};

bool has_cycle(const vector<vector<int>>& g)
{
    int n = g.size(); 
    UnionFindSet unifindset(n);
    for(int u = 0; u < n; ++u)
    {
        for(int v: g[u])
        {
            if(unifindset.same(u, v))
                return true; // 找到环
            unifindset.merge(u, v);
        }
    }
    return false; // 没有环
}

算法4: 拓扑排序

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
bool has_cycle(const vector<vector<int>>& g)
{
    int n = g.size(); // g 从 1 开始，共 n - 1 个点
    vector<int> degrees(n);
    for(int u = 0; u < n; ++u)
        degrees[u] = g[u].size();

    queue<int> q;
    vector<bool> visited(n, false);
    for(int u = 0; u < n; ++u)
        if(degrees[u] == 1)
        {
            q.push(u);
            visited[u] = true;
        }

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int v: g[u])
        {
            if(visited[v])
                continue;
            --degrees[v];
            if(degrees[v] == 1)
            {
                visited[v] = true;
                q.push(v);
            }
        }
    }

    for(int u = 0; u < n; ++u)
        if(degrees[u] > 1)
            return true;
    return false; // 没有环
}

$2 判定：边是否在环上

684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

提示:

1
2
3
4
5
6
7
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的

示例 1：

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

算法1：并查集

依次枚举边表中的边 $uv$，过程中维护并查集，若并查集中 $u,v$ 属于同一个集合，则此前枚举过的边已经构成了 $u,v$ 之间的一条路径，此时再连接边 $u, v$，则构成一个环，$uv$ 就是环上的边。

由于图的形态是树加上一条边，因此只有一个环，又因为枚举顺序是从左到右，于是 $uv$ 是环上的边在 edges 中最后出现的。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        UnionFindSet unionfindset(N);
        for(vector<int> &edge: edges)
        {
            int x = edge[0], y = edge[1];
            if(unionfindset.same(x, y))
                return vector<int>({x, y});
            else
                unionfindset.merge(x, y);
        }
        return vector<int>();
    }
};

算法2：拓扑排序

拓扑排序之后，degrees 中的所有度大于 1 的节点的任意组合都是可删的边。

代码 (C++)

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
void topsort(const vector<vector<int>>& g, vector<int>& degrees)
{
    int n = g.size(); // g 从 1 开始，共 n - 1 个点
    for(int u = 0; u < n; ++u)
        degrees[u] = g[u].size();

    queue<int> q;
    vector<bool> visited(n, false);
    for(int u = 0; u < n; ++u)
        if(degrees[u] == 1)
        {
            q.push(u);
            visited[u] = true;
        }

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int v: g[u])
        {
            if(visited[v])
                continue;
            --degrees[v];
            if(degrees[v] == 1)
            {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        vector<vector<int>> g(N + 1);
        for(const vector<int> &edge: edges)
        {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
        }

        vector<int> degrees(N + 1, 0);
        topsort(g, degrees);
        for(int i = N - 1; i >= 0; --i)
            if(degrees[edges[i][0]] > 1 && degrees[edges[i][1]] > 1)
                return edges[i];
        return {};
    }
};

685. 冗余连接 II

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

提示：

1
2
3
4
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n

示例 1：

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

算法：并查集

上一题是一棵无根树(连通无环无向图)加了一条边形成一个环，删去一条环上的边。

本题是一棵有根树(有向图，有一个根节点，其余所有点均为根的后继，除根外每个节点有且只有一个父节点)。在有根树的基础上加了一条边，我们要删除一条边，使得剩余部分形成有根树。

在有根树上新增一条边，可能会有两种情况：

一种情况是新增的边以根为终点，由于根的入度为 0，加边后所有顶点的入度均为 1，也就是对任意节点 $u$，其父节点 $fa[u]$ 存在且唯一，上图左边画的就是这种情况。此时可以将所有边视为无向边，图视为无向图，然后删掉该无向图的环上的任意一条边即可，算法与前面的 684 题一样。

另一种情况是新增的边以除根以外的另一个顶点为终点，这样该顶点的入度就会变为 2，即有两条入边。那么应该删掉的边就只能是这两条之一。上图右边画的就是这种情况。不论删掉哪一条，都会变成除了一个顶点入度为0，其余顶点入度均为1的情况，但是图可能不连通，例如上图右边被黑色圈出的两条边，如果删掉蓝色那一条，就会造成图不连通的情况。

因此我们可以直接删除一条边，然后看剩余部分视为无向图，判断其是否连通，若连通，则被删的边是答案；若不连通，则另一条边是答案。

代码 (C++)

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
90
class UnionFindSet
{
public:
    UnionFindSet(int N)
    {
        _father = vector<int>(N + 1, -1);
        _rank = vector<int>(N + 1, 1);
        for(int i = 0; i <= N; ++i)
            _father[i] = i;
    }

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);

        if(x == y) return;
        if(_rank[x] < _rank[y])
            _father[x] = y;
        else
            _father[y] = x;
        if(_rank[x] == _rank[y])
            ++_rank[x];
    }

private:
    vector<int> _father;
    vector<int> _rank;

    int _find(int x)
    {
        if(_father[x] == x) return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        vector<int> fa(N + 1, -1);
        vector<int> tmp1(2, -1);
        vector<int> tmp2(2, -1);
        for(const vector<int> &edge: edges)
        {
            if(fa[edge[1]] != -1) // 找到入度为 2 的
            {
                tmp1 = edge;
                tmp2[0] = fa[edge[1]];
                tmp2[1] = edge[1];
                break;
            }
            fa[edge[1]] = edge[0];
        }

        if(tmp1[0] == -1)
        {
            // 加边后所有节点入度均为1
            // 视为无向图删掉环上一条边即可
            UnionFindSet unionfindset(N);
            for(const vector<int> &edge: edges)
            {
                int x = edge[0], y = edge[1];
                if(unionfindset.same(x, y))
                    return edge;
                unionfindset.merge(x, y);
            }
            return vector<int>(2, -1);
        }

        // 加边后有一个顶点入度为 2
        // 删去 tmp1，看剩余部分是否连通
        UnionFindSet unionfindset(N);
        for(const vector<int> &edge: edges)
        {
            if(edge == tmp1)
                continue;
            int x = edge[0], y = edge[1];
            if(unionfindset.same(x, y))
                return tmp2;
            unionfindset.merge(x, y);
        }
        return tmp1;
    }
};

$3 判定：是否存在边数至少为4的环

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

提示：

1
2
3
4
5
m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。

示例 1：

输入：grid = [[“a”,”a”,”a”,”a”],[“a”,”b”,”b”,”a”],[“a”,”b”,”b”,”a”],[“a”,”a”,”a”,”a”]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：

示例 2：

输入：grid = [[“c”,”c”,”c”,”a”],[“c”,”d”,”c”,”c”],[“c”,”c”,”e”,”c”],[“f”,”c”,”c”,”c”]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

输入：grid = [[“a”,”b”,”b”],[“b”,”z”,”b”],[“b”,”b”,”a”]]
输出：false

算法：DFS

我们要判断无向无权图上是否存在长度大于等于 4 的环。

在无向图上判定环的 DFS 算法的基础上，维护额外信息: d[u] := u 到源点 start 的距离，在判定到环上的边时候，多一步距离的判断：边上的两点到源的距离：

1
2
3
4
5
6
7
if(visited[x][y])
{
    // 找到环 (x, y) -> ... -> (i, j) -> (x, y)
    if(dist[i][j] - dist[x][y] + 1 >= 4)
        return true;
    continue;
}

代码 (C++)

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
class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        vector<vector<int>> dist(n, vector<int>(m, 0));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(visited[i][j])
                    continue;
                visited[i][j] = true;
                dist[i][j] = 1;
                if(dfs(grid, i, j, visited, dist))
                    return true;
            }
        return false;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    bool dfs(const vector<vector<char>>& grid, int i, int j, vector<vector<bool>>& visited, vector<vector<int>>& dist)
    {
        int n = grid.size(), m = grid[0].size();
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            if(x < 0 || x >= n || y < 0 || y >= m)
                continue;
            if(grid[x][y] != grid[i][j])
                continue;
            if(visited[x][y])
            {
                if(dist[i][j] - dist[x][y] + 1 >= 4)
                    return true;
                continue;
            }
            visited[x][y] = true;
            dist[x][y] = dist[i][j] + 1;
            if(dfs(grid, x, y, visited, dist))
                return true;
        }
        return false;
    }
};
Share