最小生成树prim算法C++
时间: 2023-11-30 11:42:20 浏览: 43
以下是C++实现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; // 如果当前生成树不连通,则返回-1
if (i) res += dist[t]; // 将当前点加入生成树,并将边的权值加入res
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"); // 如果当前图不连通,则输出impossible
else cout << t << endl; // 输出最小生成树的权值和
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)