帮我用c语言下一个prim算法
时间: 2024-09-16 16:05:04 浏览: 41
Prim算法是一种用于求解最小生成树的贪心算法,常用于图论中。以下是使用C语言实现Prim算法的一个基本版本:
```c
#include <stdio.h>
#include <stdlib.h>
#define V 9 // 图的顶点数,这里假设是一个较小的值
// 定义邻接矩阵表示图
int graph[V][V] = {
{0, 2, 0, 6, 0, 0, 2, 0, 0},
{2, 0, 3, 8, 5, 0, 0, 7, 4},
{0, 3, 0, 0, 0, 4, 0, 0, 0},
{6, 8, 0, 0, 7, 0, 4, 0, 0},
{0, 5, 0, 7, 0, 9, 0, 0, 10},
{0, 0, 4, 0, 9, 0, 11, 0, 0},
{2, 0, 0, 4, 0, 11, 0, 1, 6},
{0, 7, 0, 0, 0, 0, 1, 0, 5},
{0, 4, 0, 0, 10, 0, 6, 5, 0}
};
// 函数声明
void primMST(int src);
int main() {
int i, j;
primMST(0); // 从第一个顶点开始
printf("Minimum Spanning Tree (MST): \n");
for (i = 0; i < V; ++i) {
for (j = 0; j < V; ++j)
if (graph[i][j] != 0 && graph[i][j] == min_weight_edge)
printf("%d - %d with weight: %d\n", i, j, graph[i][j]);
}
return 0;
}
// 辅助函数:找到源节点到其他所有节点中最短边
void primMST(int src) {
int key[V], i, u, v, min_weight_edge;
// 初始化关键集key[]和最短路径集合parent[]
for (i = 0; i < V; ++i)
key[i] = INT_MAX, parent[i] = -1;
// 将src设为关键集中的最低权重
key[src] = 0;
min_weight_edge = INT_MAX;
// 遍历所有节点直到关键集包含所有节点
while (true) {
// 找到当前关键集中权重最小的未加入关键集的顶点u
u = -1;
for (i = 0; i < V; ++i) {
if (key[i] < min_weight_edge && parent[i] == -1) {
u = i;
min_weight_edge = key[u];
}
}
// 若找不到这样的顶点,说明关键集已包含所有节点,结束循环
if (u == -1)
break;
// 更新相邻顶点v的关键集key[v]
for (v = 0; v < V; ++v)
if (graph[u][v] && graph[u][v] < key[v] && parent[v] == -1)
key[v] = graph[u][v];
// 更新parent数组,记录每个节点到达关键集的最近祖先
parent[u] = src;
}
}
```
阅读全文