一刷代码随想录（图论7）

本文主要是介绍一刷代码随想录（图论7），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目引入：

题目描述：

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

输入描述：

第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。

接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。

输出描述：

输出联通所有岛屿的最小路径总距离

输入示例：

7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1

输出示例：

6

解题方法：

本题是求最小生成树的问题：

最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。

图中有n个节点，那么一定可以用 n - 1 条边将所有节点连接到一起。

那么如何选择 这 n-1 条边 就是 最小生成树算法的任务所在。

1、prim算法求解最小生成树

prim三部曲

1. 第一步，选距离生成树最近节点
2. 第二步，最近节点加入生成树
3. 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

，minDist数组代表所有节点距离当前最小生成树的距离

1、初始状态，首先将minDist初始化成距离最大值。

2、使用prim三部曲构造最小生成树，首先将第一个点加入最小生成树，之后不断重复prim三部曲。

3、最后每次更新minDist数组时将边记录方便打印。

代码：

#include<iostream>
#include<vector>
#include <climits>using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;grid[x][y] = k;grid[y][x] = k;}vector<int> minDist(v + 1, 10001);vector<bool> isInTree(v + 1, false);//加上初始化vector<int> parent(v + 1, -1);for (int i = 1; i < v; i++) {int cur = -1;int minVal = INT_MAX;for (int j = 1; j <= v; j++) {if (!isInTree[j] &&  minDist[j] < minVal) {minVal = minDist[j];cur = j;}}isInTree[cur] = true;for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];parent[j] = cur; // 记录边}}}// 输出 最小生成树边的链接情况for (int i = 1; i <= v; i++) {cout << i << "->" << parent[i] << endl;}
}

2、K算法，与上方不同，K算法管理的的是节点之间的边，首先将节点的边进行排序，先将小的边加入生成树，并将两个节点加入并查集，并每一次都对两个节点进行判断，若发现两个已经在并查集，证明如果加入后会成环，不会加入最小生成树。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct Edge {int l, r, val;
};int n = 10001;vector<int> father(n, -1); void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); 
}void join(int u, int v) {u = find(u); v = find(v); if (u == v) return ; father[v] = u;
}int main() {int v, e;int v1, v2, val;vector<Edge> edges;int result_val = 0;cin >> v >> e;while (e--) {cin >> v1 >> v2 >> val;edges.push_back({v1, v2, val});}sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});vector<Edge> result; // 存储最小生成树的边init();for (Edge edge : edges) {int x = find(edge.l);int y = find(edge.r);if (x != y) {result.push_back(edge); // 保存最小生成树的边result_val += edge.val; join(x, y);}}// 打印最小生成树的边for (Edge edge : result) {cout << edge.l << " - " << edge.r << " : " << edge.val << endl;}return 0;
}

Prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。

这篇关于一刷代码随想录（图论7）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---