prim算法的c++实现
时间: 2023-10-30 08:20:12 浏览: 38
以下是Prim算法的C++实现:
```c++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005; // 最大点数
const int INF = 0x3f3f3f3f;
int n; // 点数
int w[MAXN][MAXN]; // 图的邻接矩阵
int dis[MAXN]; // 存储最小生成树到每个点的距离
bool vis[MAXN]; // 标记点是否已经被加入最小生成树
int prim()
{
memset(dis, INF, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[1] = 0; // 从1号点开始
int ans = 0; // 最小生成树的边权之和
for (int i = 1; i <= n; i++)
{
int x = 0;
for (int j = 1; j <= n; j++)
{
if (!vis[j] && (x == 0 || dis[j] < dis[x]))
{
x = j; // 找到未访问过的距离最小的点
}
}
vis[x] = true;
ans += dis[x];
for (int y = 1; y <= n; y++)
{
if (!vis[y] && w[x][y] < dis[y])
{
dis[y] = w[x][y]; // 更新最小生成树到每个点的距离
}
}
}
return ans;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> w[i][j];
}
}
int ans = prim();
cout << ans << endl;
return 0;
}
```
注意:该实现假设图是连通的,如果图不连通,则需要对每个连通块分别进行Prim算法。