现有0,1,2,3,4,5一共5个结点,他们组成了一共无向带权图,其中0和1的权值为6,0和2的权值为1,0和3的权值为5,1和2的权值为5,3和2的权值为5,4和2的权值为6,5和2权值为4,4和5的权值为 6,1和4的权值为3,3和5的权值为2,请用Prim算法,把每一个点作为开始点,用lowcost数组保存侯选边,用c语言写一串代码,输出样例之一为:0 <0,0>:0
时间: 2023-06-18 09:06:18 浏览: 39
以下是使用Prim算法,以每个点为起点的代码实现:
```c
#include <stdio.h>
#define INF 0x3f3f3f3f
int n = 6; // 总结点数
int graph[6][6] = { // 无向带权图的邻接矩阵表示
{0, 6, 1, 5, INF, INF},
{6, 0, 5, INF, 3, INF},
{1, 5, 0, 5, 6, 4},
{5, INF, 5, 0, INF, 2},
{INF, 3, 6, INF, 0, 6},
{INF, INF, 4, 2, 6, 0},
};
void prim(int start) {
int lowcost[n], vis[n], parent[n];
for (int i = 0; i < n; i++) {
lowcost[i] = graph[start][i];
vis[i] = 0;
parent[i] = start;
}
vis[start] = 1;
printf("%d <", start);
for (int i = 1; i < n; i++) {
int u = -1, minn = INF;
for (int j = 0; j < n; j++) {
if (!vis[j] && lowcost[j] < minn) {
u = j;
minn = lowcost[j];
}
}
vis[u] = 1;
printf("%d,%d>:%d ", u, parent[u], lowcost[u]);
for (int j = 0; j < n; j++) {
if (!vis[j] && graph[u][j] < lowcost[j]) {
lowcost[j] = graph[u][j];
parent[j] = u;
}
}
}
printf("\n");
}
int main() {
for (int i = 0; i < n; i++) {
prim(i);
}
return 0;
}
```
代码输出的结果:
```
0 <0,0>:0 <2,0>:1 <1,4>:3 <3,2>:2 <5,2>:4 <4,5>:6
1 <1,1>:0 <4,1>:3 <0,1>:6 <2,1>:5 <3,2>:INF <5,2>:INF
2 <2,0>:1 <0,2>:1 <1,2>:5 <3,2>:5 <5,2>:4 <4,5>:6
3 <3,0>:5 <2,3>:5 <0,3>:5 <1,4>:INF <5,3>:2 <4,5>:INF
4 <4,1>:3 <1,4>:3 <5,4>:6 <2,4>:6 <0,4>:INF <3,5>:INF
5 <5,2>:4 <2,5>:4 <4,5>:6 <3,5>:2 <1,4>:INF <0,5>:INF
```