摘要: 无线图最小环问题:Floyd变形、Dijkstra变形
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】 我的网站:潮汐朝夕的生活实验室 我的公众号:算法题刷刷 我的知乎:潮汐朝夕 我的github:FennelDumplings 我的leetcode:FennelDumplings
本文我们看一下无向图中求长度最短的环的问题。
如果无向图是带权的,那么算法是在 Floyd 求最短路径的过程中对最小环的长度进行更新,时间复杂度与 Floyd 最短路径算法相同,为 O ( V 3 ) ;
如果无向图是无权的,那么算法是在 BFS 求最短路径的过程中对最小环的长度进行更新,但是需要以每个节点都作为起点走一遍 BFS,BFS 的时间复杂度为 O ( V + E ) ,于是总时间复杂度为 O ( V 2 + V E ) 。
带权无向图,长度最短的环 求最小环的长度
给定一张无向图,求图中一个至少包含 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 求最小环。
min 1 ≤ i < j < k { d [ i ] [ j ] + a d j [ j ] [ k ] + a d j [ k ] [ i ] } 即为满足以下两个条件的最小环长度:
由编号不超过 k 的节点组成
经过节点 k
推导过程与最短路径的 Floyd 算法类似,k 为阶段,表示当前考虑的是由小于等于 k 的节点构成的子图。i , j 为附加信息。
假设当前推导到了阶段 k ,此时 d [ i ] [ j ] 表示由编号小于 k 的节点组成的 i 到 j 的最短路径。因此 min 1 ≤ i < j < k { d [ i ] [ j ] + a d j [ j ] [ k ] + a d j [ k ] [ i ] } 即为经过节点 k 的由不超过 k 的节点组成的最小环。
按照 Floyd 最短路径算法,应该在阶段 k 上枚举 1 ≤ i , j ≤ N 并更新 d [ i ] [ j ] 。在此之前,先枚举 1 ≤ i < j < k 并用 d [ i ] [ j ] + a d j [ j ] [ k ] + a d j [ 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 ,总长度 2 k + 1 。注意 s 到 u 和 v 到 s 中可能有某些边是重合的,重复计数了,所得长度会偏长。不过后续每个节点都会作为起点走一遍 BFS,在取最小值的时候会排除掉重复计算的这部分边。将 2 k + 1 更新进答案后,跳过。
v 是下一层,也就是第 k + 1 层的节点,并且此前尚未被访问过,即该节点第一次被访问到,直接压入队列即可;
v 是下一层,也就是第 k + 1 层的节点,但此前访问过该节点,那么我们把以下路径视为一个环:从 s 走 k + 1 步到 v ,从 v 走 k + 1 步到 s ,总长度 2 k + 2 。s 到 u 和 v 到 s 中可能有某些边是重合的,重复计数了,所得长度会偏长。后续每个节点都会作为起点走一遍 BFS,在取最小值的时候会排除掉重复计算的这部分边。将 2 k + 2 更新进答案后,跳过。
在 BFS 的过程中维护 l e v e l ,l e v e l [ u ] 表示节点 u 在 BFS 过程中的所在层,若 l e v e l [ 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; } };