最小生成树代码c++
时间: 2023-12-10 10:34:52 浏览: 33
以下是C++实现Prim算法和Kruskal算法求解最小生成树的代码:
1. Prim算法
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int g[N][N]; // 存储图的邻接矩阵
int dist[N]; // 存储当前点到最小生成树的距离
bool st[N]; // 存储当前点是否已经加入最小生成树
int prim(int n)
{
memset(dist, 0x3f, sizeof dist); // 初始化dist数组为无穷大
int res = 0; // 存储最小生成树的权值和
for (int i = 0; i < n; i ++ )
{
int t = -1; // 存储当前距离最小生成树最近的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == 0x3f3f3f3f) return -1; // 无法构成最小生成树
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main()
{
int n, m;
cin >> n >> m;
memset(g, 0x3f, sizeof g); // 初始化邻接矩阵为无穷大
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c); // 无向图存储
}
int t = prim(n);
if (t == -1) puts("impossible");
else cout << t << endl;
return 0;
}
```
2. Kruskal算法
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int p[N]; // 并查集数组
struct Edge
{
int a, b, w;
bool operator< (const Edge &W) const
{
return w < W.w;
}
}edges[N]; // 存储边的信息
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal(int n, int m)
{
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
sort(edges, edges + m); // 将边按权值从小到大排序
int res = 0, cnt = 0; // res存储最小生成树的权值和,cnt存储当前加入最小生成树的边数
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个点不在同一个连通块中,则将它们合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return -1; // 无法构成最小生成树
return res;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i ++ )
cin >> edges[i].a >> edges[i].b >> edges[i].w;
int t = kruskal(n, m);
if (t == -1) puts("impossible");
else cout << t << endl;
return 0;
}
```