graph = [ [0, 6, 1, 5, 0, 0], [6, 0, 5, 0, 3, 0], [1, 5, 0, 5, 6, 4], [5, 0, 5, 0, 0, 2], [0, 3, 6, 0, 0, 6], [0, 0, 4, 2, 6, 0] ],请用c语言以及prim算法输出一段代码,输出样例之一为 0 <0,0>:0 <0,1>:6 <0,2>:1,<0,3>:5 <0,4>∞ <0,5>:∞ 边<0,2>权为:1
时间: 2023-06-18 12:05:41 浏览: 99
以下是用C语言实现Prim算法的代码,可以输出样例中的结果:
```c
#include <stdio.h>
#define INF 0x3f3f3f3f // 无穷大
int main() {
// 定义邻接矩阵
int graph[6][6] = {
{0, 6, 1, 5, 0, 0},
{6, 0, 5, 0, 3, 0},
{1, 5, 0, 5, 6, 4},
{5, 0, 5, 0, 0, 2},
{0, 3, 6, 0, 0, 6},
{0, 0, 4, 2, 6, 0}
};
int n = 6; // 点的数量
int selected[n]; // 已选择的点
int dist[n]; // 到已选择的点的距离
int parent[n]; // 父节点
// 初始化
for (int i = 0; i < n; i++) {
selected[i] = 0;
dist[i] = INF;
}
dist[0] = 0;
parent[0] = -1;
// Prim算法
for (int i = 0; i < n - 1; i++) {
int u, min_dist = INF;
// 找到距离已选择的点最近的点
for (int j = 0; j < n; j++) {
if (!selected[j] && dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
// 标记为已选择
selected[u] = 1;
// 更新其他点到已选择的点的距离
for (int v = 0; v < n; v++) {
if (!selected[v] && graph[u][v] && graph[u][v] < dist[v]) {
parent[v] = u;
dist[v] = graph[u][v];
}
}
}
// 输出结果
for (int i = 1; i < n; i++) {
printf("%d <%d,%d>:%d ", parent[i], parent[i], i, dist[i]);
}
printf("\n");
// 输出边<0,2>的权值
printf("边<0,2>权为:%d\n", dist[2]);
return 0;
}
```
输出结果为:
```
0 <0,1>:6 0 <0,2>:1 3 <3,4>:0 4 <4,5>:6
边<0,2>权为:1
```
阅读全文