算法图算法

无向图的最小环问题

字数统计: 2.5k字   |   阅读时长: 11分
, ,

摘要: 无线图最小环问题：Floyd变形、Dijkstra变形

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

本文我们看一下无向图中求长度最短的环的问题。

如果无向图是带权的，那么算法是在 Floyd 求最短路径的过程中对最小环的长度进行更新，时间复杂度与 Floyd 最短路径算法相同，为 $O(V^{3})$；

如果无向图是无权的，那么算法是在 BFS 求最短路径的过程中对最小环的长度进行更新，但是需要以每个节点都作为起点走一遍 BFS，BFS 的时间复杂度为 $O(V + E)$，于是总时间复杂度为 $O(V^{2} + VE)$。

带权无向图，长度最短的环

求最小环的长度

给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。

1
2
3
4
5
6
7
8
9
10
11
输入格式
第一行两个正整数 n,m 表示点数和边数。
接下来 m 行，每行三个正整数 u,v,d，表示节点 u,v 之间有一条长度为 d 的边。

输出格式
输出边权和最小的环的边权和。若无解，输出 No solution.。

数据范围
对于 20% 的数据，n,m<=10。
对于 60% 的数据，m<=100。
对于 100% 的数据，1<=n<=100，1<=m<=5e3 1<=d<=1e5

输入输出样例
输入
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
输出
61

算法：Floyd

参考 Floyd算法，考虑 Floyd 的过程：

在最外层 k 在迭代过程中，迭代到 k 时，d[i][j] 表示经过编号不超过 k - 1 的节点，从 i 到 j 的最短路径，基于这个事实，可以用 Floyd 求最小环。

即为满足以下两个条件的最小环长度：

  1. 由编号不超过 k 的节点组成
  2. 经过节点 k

推导过程与最短路径的 Floyd 算法类似，$k$ 为阶段，表示当前考虑的是由小于等于 $k$ 的节点构成的子图。$i,j$ 为附加信息。

假设当前推导到了阶段 $k$，此时 $d[i][j]$ 表示由编号小于 $k$ 的节点组成的 $i$ 到 $j$ 的最短路径。因此 $\min\limits_{1 \leq i < j < k} \{d[i][j] + adj[j][k] + adj[k][i]\}$ 即为经过节点 $k$ 的由不超过 $k$ 的节点组成的最小环。

按照 Floyd 最短路径算法，应该在阶段 $k$ 上枚举 $1 \leq i, j \leq N$ 并更新 $d[i][j]$。在此之前，先枚举 $1 \leq i < j < k$ 并用 $d[i][j] + adj[j][k] + adj[k][i]$ 更新最小环的答案即可。

时间复杂度与最短路径的 Floyd 算法相同，为 $O(N^{3})$。

代码 (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
#include <vector>
#include <climits>
#include <iostream>

using namespace std;
using ll = long long;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int> > adj(N + 1, vector<int>(N + 1, INT_MAX / 2));
    for(int i = 1; i <= M; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        if(u < 1 || u > N || v < 1 || v > N) continue;
        adj[u][v] = min(adj[u][v], w);
        adj[v][u] = min(adj[v][u], w);
    }
    for(int i = 1; i <= N; ++i)
        adj[i][i] = 0;
    vector<vector<int> > d = adj;
    int ans = INT_MAX / 2;
    for(int k = 1; k <= N; ++k)
    {
        for(int i = 1; i < k; ++i)
            for(int j = i + 1; j < k; ++j)
                ans = min((ll)ans, (ll)d[i][j] + adj[j][k] + adj[k][i]);
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
                d[i][j] = min((ll)d[i][j], (ll)d[i][k] + d[k][j]);
    }
    if(ans == INT_MAX / 2)
        cout << "No solution." << endl;
    else
        cout << ans << endl;
}

求具体的最小环

问题：

给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

算法：Floyd

在 Floyd 算法求最小环的算法的基础上。参考 求具体的最优决策序列，在动态规划的过程中维护最优决策序列即可。

代码 (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
#include <vector>
#include <climits>
#include <iostream>

using namespace std;

void get_path(vector<int>& path, int x, int y, const vector<vector<int>>& pos)
{
    if(pos[x][y] == 0) return;
    get_path(path, x, pos[x][y], pos);
    path.push_back(pos[x][y]);
    get_path(path, pos[x][y], y, pos);
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> adj(N + 1, vector<int>(N + 1, INT_MAX / 2));
    for(int i = 1; i <= M; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        if(u < 1 || u > N || v < 1 || v > N) continue;
        adj[u][v] = min(adj[u][v], w);
        adj[v][u] = min(adj[v][u], w);
    }
    for(int i = 1; i <= N; ++i)
        adj[i][i] = 0;
    vector<vector<int>> d = adj;
    int ans = INT_MAX / 2;
    vector<int> path;
    vector<vector<int>> pos(N + 1, vector<int>(N + 1, 0));
    for(int k = 1; k <= N; ++k)
    {
        for(int i = 1; i < k; ++i)
            for(int j = i + 1; j < k; ++j)
            {
                if(ans > (long long)d[i][j] + adj[j][k] + adj[k][i])
                {
                    ans = d[i][j] + adj[j][k] + adj[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(path, i, j, pos);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
            {
                if(d[i][j] > d[i][k] + d[k][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                    pos[i][j] = k;
                }
            }
    }
    if(ans == INT_MAX / 2)
        cout << "No solution." << endl;
    else
    {
        for(int i: path) cout << i << " ";
        cout << endl;
    }
}

无权无向图，边数最少的环

现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。

返回图中 最短 环的长度。如果不存在环，则返回 -1 。

环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

提示：

1
2
3
4
5
6
2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= ui, vi < n
ui != vi
不存在重复的边

示例 1：

输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出：3
解释：长度最小的循环是：0 -> 1 -> 2 -> 0

示例 2：

输入：n = 4, edges = [[0,1],[0,2]]
输出：-1
解释：图中不存在循环

算法：BFS

从起点 $s$ 出发进行 BFS，起点 $s$ 为第 0 层，假设当前进行到第 $k$ 层，该层有若干节点，对于节点 $u$，考查与 $u$ 相邻的节点 $v$，有三种可能情况：

  • $v$ 是上一层，也就是第 $k-1$ 层的节点，直接跳过即可；
  • $v$ 与 $u$ 一样，是第 $k$ 层的节点，此时我们把以下路径视为一个环：从 $s$ 走 $k$ 步到 $u$，从 $u$ 走 1 步到 $v$，从 $v$ 走一步到 $s$，总长度 $2k + 1$。注意 $s$ 到 $u$ 和 $v$ 到 $s$ 中可能有某些边是重合的，重复计数了，所得长度会偏长。不过后续每个节点都会作为起点走一遍 BFS，在取最小值的时候会排除掉重复计算的这部分边。将 $2k+1$ 更新进答案后，跳过。
  • $v$ 是下一层，也就是第 $k+1$ 层的节点，并且此前尚未被访问过，即该节点第一次被访问到，直接压入队列即可；
  • $v$ 是下一层，也就是第 $k+1$ 层的节点，但此前访问过该节点，那么我们把以下路径视为一个环：从 $s$ 走 $k+1$ 步到 $v$，从 $v$ 走 $k+1$ 步到 $s$，总长度 $2k + 2$。$s$ 到 $u$ 和 $v$ 到 $s$ 中可能有某些边是重合的，重复计数了，所得长度会偏长。后续每个节点都会作为起点走一遍 BFS，在取最小值的时候会排除掉重复计算的这部分边。将 $2k+2$ 更新进答案后，跳过。

在 BFS 的过程中维护 $level$，$level[u]$ 表示节点 $u$ 在 BFS 过程中的所在层，若 $level[u] = -1$ 则表示 $u$ 尚未被访问。

这样一轮 BFS 后，就得到经过点 $s$ 的最小环的长度，将所有节点都作为起点走一遍 BFS，即得图的最小环长度。

代码 (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
int bfs(const vector<vector<int>>& g, int s)
{
    int n = g.size();
    vector<int> level(n, -1);
    queue<int> q;
    q.push(s);
    level[s] = 0;
    int k = 0;
    int ans = INT_MAX / 2;
    vector<int> level_nodes;
    while(!q.empty())
    {
        level_nodes.clear();
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int v: g[u])
            {
                if(level[v] == -1)
                {
                    level_nodes.push_back(v);
                    level[v] = k + 1;
                }
                else if(level[v] == k + 1)
                {
                    ans = min(ans, 2 * k + 2);
                }
                else if(level[v] == k)
                {
                    ans = min(ans, 2 * k + 1);
                }
            }
        }
        if(ans != INT_MAX / 2)
            return ans;
        for(int u: level_nodes)
            q.push(u);
        k++;
    }
    return ans;
}

class Solution {
public:
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n, vector<int>());
        for(vector<int>& e: edges)
        {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        int ans = INT_MAX / 2;
        for(int s = 0; s < n; ++s)
        {
            ans = min(ans, bfs(g, s));
        }
        if(ans == INT_MAX / 2)
            return -1;
        return ans;
    }
};
Share