prim算法用c++实现
时间: 2023-11-04 19:17:56 浏览: 42
下面是使用C语言实现Prim算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define INF 0x3f3f3f3f
#define MAXN 100
int graph[MAXN][MAXN]; // 图的邻接矩阵
int n; // 图中节点的数量
int Prim() {
int i, j, u, v;
int min, sum = 0;
int lowcost[MAXN]; // 记录到集合的最小边权值
int closest[MAXN]; // 记录到集合的最小边所连接的节点
// 初始化lowcost和closest数组
for (i = 1; i < n; i++) {
lowcost[i] = graph[0][i];
closest[i] = 0;
}
// 将节点0加入集合
closest[0] = -1;
for (i = 1; i < n; i++) {
min = INF;
u = -1;
// 找到到集合最近的节点
for (j = 0; j < n; j++) {
if (closest[j] != -1 && lowcost[j] < min) {
min = lowcost[j];
u = j;
}
}
// 将节点加入集合
closest[u] = -1;
sum += min;
// 更新lowcost和closest数组
for (v = 0; v < n; v++) {
if (closest[v] != -1 && graph[u][v] < lowcost[v]) {
lowcost[v] = graph[u][v];
closest[v] = u;
}
}
}
return sum;
}
int main() {
int i, j, weight;
scanf("%d", &n);
// 读入图的邻接矩阵
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &weight);
graph[i][j] = weight;
}
}
int minCost = Prim();
printf("最小生成树的权值为:%d\n", minCost);
return 0;
}
```
该程序中使用邻接矩阵存储图的信息,并使用了两个数组`lowcost`和`closest`来记录到集合的最小边权值和最小边所连接的节点。程序的时间复杂度为$O(n^2)$,对于较小的图可以得到较好的运行效率。