prim算法求最小生成树c
时间: 2023-07-22 17:04:35 浏览: 45
以下是使用Prim算法求解最小生成树的C语言代码,假设图的顶点数为n,边数为m,边权存储在邻接矩阵中:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
#define INF 0x3f3f3f3f
int graph[MAXN][MAXN]; // 邻接矩阵表示图
int dis[MAXN]; // 存储每个顶点到生成树的距离
int vis[MAXN]; // 标记每个顶点是否已经加入生成树
int prim(int n) {
int i, j, u, min, sum = 0;
// 初始化dis数组和vis数组
for (i = 0; i < n; i++) {
dis[i] = graph[0][i];
vis[i] = 0;
}
vis[0] = 1; // 将第一个顶点加入生成树
for (i = 1; i < n; i++) { // 循环n-1次,每次加入一个顶点
min = INF;
// 找到距离生成树最近的顶点
for (j = 0; j < n; j++) {
if (!vis[j] && dis[j] < min) {
min = dis[j];
u = j;
}
}
vis[u] = 1; // 将该顶点加入生成树
sum += min; // 更新生成树的权值和
// 更新dis数组
for (j = 0; j < n; j++) {
if (!vis[j] && graph[u][j] < dis[j]) {
dis[j] = graph[u][j];
}
}
}
return sum;
}
int main() {
int n, m, i, j, u, v, w;
scanf("%d%d", &n, &m);
// 初始化邻接矩阵
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = INF;
}
}
// 读入边的信息
for (i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = graph[v][u] = w;
}
printf("%d\n", prim(n)); // 输出最小生成树的权值和
return 0;
}
```
其中,dis数组存储每个顶点到生成树的距离,vis数组标记每个顶点是否已经加入生成树。算法的主要流程如下:
1. 初始化dis数组和vis数组;将第一个顶点加入生成树。
2. 循环n-1次,每次找到距离生成树最近的顶点,将其加入生成树,并更新dis数组。
3. 输出最小生成树的权值和。
时间复杂度为O(n^2)。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)