所谓的最小生成树，就是给你一个连通图，你需要求出其极小连通子图：图中的每个点都需要包含在内，且整体的权值尽可能的小。和最短路径的区别是：最小生成树保证整个拓扑图的权值之和为最小，但不保证两点之间的距离最小。
一般有两种算法来解决这类问题：Prim算法和Kruskal算法，它们都是基于贪心算法实现的，不同的是，Prim算法从顶点入手，寻找最小边。而Kruskal是直接从边入手，将边(edge)进行排序之后，通过判断是否成环来进行挑选。直接来看动画演示吧。
Prim算法
最开始时，存储最小生成树（MST）的集合中没有元素，而另一个集合表示不在MST中的点，在算法运行的过程中，MST集合会越来越大，而另一个集合会越来越小，最终只存在MST集合，即为最终的答案。算法详细过程如下：
题目链接：https://www.acwing.com/problem/content/860/
#include<iostream>
#include<cstring>
using namespace std;
const int N = 550;
int dist[N];
bool vis[N];
int n, m;
int map[N][N];
int prim() {
memset(dist, 0x3f, sizeof dist);
int res = 0;
for(int i = 0; i < n; ++i) {
int t = -1;
for(int j = 1; j <= n; ++j) {
if(!vis[j] && (t == -1 || dist[j] < dist[t])) { //寻找最短的边
t = j;
}
}
if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f; //如果不是第一条边且不连通，那说明构不成最小生成树
if(i) res += dist[t]; //只要不是第一条边，那么就可以加到res中
vis[t] = true; //设置为访问过
for(int j = 1; j <= n; ++j) //使用当前的边去更新其他边
dist[j] = min(dist[j], map[t][j]);
}
return res;
}
int main() {
memset(map, 0x3f, sizeof map);
cin >> n >> m;
while(m -- ) {
int a, b, c;
cin >> a >> b >> c;
map[a][b] = map[b][a] = min(map[a][b], c);
}
int t = prim();
if(t == 0x3f3f3f3f) cout <<"impossible" << endl;
else cout << t << endl;
return 0;
}
Kruskal算法
将边的权值进行从小到大排序之后，首先考虑权值小的边，如果这条边和当前以选顶点不构成环，则说明可以选。所以我们现在只需要考虑如果判断构成环就行了。我之前讲过一个数据结构就是专门来判断这类问题的，直接用并查集维护就行了。
详细的算法过程：
题目链接：https://www.acwing.com/problem/content/861/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e6 + 10;
struct edge {
int x, y, w;
bool operator < (const edge & W) const {
return w < W.w;
}
} edges[M];
int fa[N];
int n, m;
int find(int x) {
if(x != fa[x]) return fa[x] = find(fa[x]);
}
int kruskal() {
sort(edges, edges + m); //对边进行排序
for(int i = 1; i <= n; ++i) fa[i] = i; //初始化并查集
int ans = 0, cnt = 0;
for(int i = 0; i < m; ++i) { //对于每条边
int a = edges[i].x, b = edges[i].y, c = edges[i]. w;
a = find(a), b = find(b);
if(a != b) { //如果a和b不在同一个集合中，那说明没环，所以可以把他们放在一个集合中
fa[a] = b;
ans += c; //答案加上权值
cnt ++; //节点个数加加
}
}
if(cnt < n - 1) return 0x3f3f3f3f; //当前的点不够，说明有的点被孤立了，所以不能构成一颗树
return ans;
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
int t = kruskal();
if(t == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
个人觉得kruskal比prim要稍微简单一点，所以kruskal可以重点学习一下。
Comments | NOTHING