用C语言编写程序求图的最小生成树算法。
时间: 2024-03-09 17:19:42 浏览: 27
下面是使用Prim算法求解图的最小生成树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000
typedef struct {
int weight;
int visited;
} Edge;
Edge graph[MAX_VERTICES][MAX_VERTICES];
int n_vertices;
int min_edge_index(Edge edges[], int n)
{
int i, min_index;
int min_weight = INT_MAX;
for (i = 0; i < n; i++) {
if (!edges[i].visited && edges[i].weight < min_weight) {
min_weight = edges[i].weight;
min_index = i;
}
}
return min_index;
}
void prim()
{
int i, j, k;
Edge edges[MAX_VERTICES];
int min_weight = 0;
for (i = 1; i < n_vertices; i++) {
edges[i].weight = INT_MAX;
edges[i].visited = 0;
}
for (i = 0; i < n_vertices-1; i++) {
int u = min_edge_index(edges, n_vertices);
edges[u].visited = 1;
min_weight += edges[u].weight;
for (j = 0; j < n_vertices; j++) {
if (graph[u][j].weight && !edges[j].visited && graph[u][j].weight < edges[j].weight) {
edges[j].weight = graph[u][j].weight;
}
}
}
printf("Minimum weight of the spanning tree: %d\n", min_weight);
}
int main()
{
int i, j;
scanf("%d", &n_vertices);
for (i = 0; i < n_vertices; i++) {
for (j = 0; j < n_vertices; j++) {
scanf("%d", &graph[i][j].weight);
graph[i][j].visited = 0;
}
}
prim();
return 0;
}
```
其中,`graph`数组表示图的邻接矩阵,`n_vertices`表示顶点数。`min_edge_index`函数找到当前未访问的边中权值最小的边的索引。`prim`函数实现了Prim算法,通过不断选取最小权值的边来构造最小生成树。最终输出最小生成树的权值和。