c语言写一个最小生成树。
时间: 2023-07-22 09:31:43 浏览: 40
下面是使用Prim算法和邻接矩阵实现最小生成树的C语言代码,供您参考。
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100 // 最大点数
#define INF 1000 // 代表无穷大
// 邻接矩阵结构体
typedef struct {
int vertices[MAX_VERTICES]; // 点集合
int edges[MAX_VERTICES][MAX_VERTICES]; // 边集合
int num_vertices; // 点数
int num_edges; // 边数
} Graph;
// 初始化邻接矩阵图
void init_graph(Graph *g) {
int i, j;
g->num_vertices = 0;
g->num_edges = 0;
for (i = 0; i < MAX_VERTICES; i++) {
g->vertices[i] = 0;
for (j = 0; j < MAX_VERTICES; j++) {
g->edges[i][j] = INF;
}
}
}
// 添加边
void add_edge(Graph *g, int u, int v, int w) {
g->edges[u][v] = w;
g->edges[v][u] = w; // 无向图
g->num_edges++;
}
// Prim算法实现最小生成树
void prim(Graph *g) {
int i, j, k, min;
int lowcost[MAX_VERTICES]; // 存储到当前生成树的最小距离
int closest[MAX_VERTICES]; // 存储当前生成树中与其它点最近的点
bool visited[MAX_VERTICES]; // 标记是否已加入生成树
// 初始化
for (i = 1; i < g->num_vertices; i++) {
lowcost[i] = g->edges[0][i];
closest[i] = 0;
visited[i] = false;
}
visited[0] = true;
// 开始构建最小生成树
for (i = 1; i < g->num_vertices; i++) {
min = INF;
// 找到到当前生成树的最短距离
for (j = 1; j < g->num_vertices; j++) {
if (!visited[j] && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
// 将当前最短距离的点加入生成树
visited[k] = true;
printf("(%d, %d)\n", closest[k], k);
// 更新lowcost和closest数组
for (j = 1; j < g->num_vertices; j++) {
if (!visited[j] && g->edges[k][j] < lowcost[j]) {
lowcost[j] = g->edges[k][j];
closest[j] = k;
}
}
}
}
int main() {
Graph g;
int i;
init_graph(&g);
g.num_vertices = 7;
for (i = 0; i < g.num_vertices; i++) {
g.vertices[i] = i;
}
add_edge(&g, 0, 1, 7);
add_edge(&g, 0, 3, 5);
add_edge(&g, 1, 2, 8);
add_edge(&g, 1, 3, 9);
add_edge(&g, 1, 4, 7);
add_edge(&g, 2, 4, 5);
add_edge(&g, 3, 4, 15);
add_edge(&g, 3, 5, 6);
add_edge(&g, 4, 5, 8);
add_edge(&g, 4, 6, 9);
add_edge(&g, 5, 6, 11);
prim(&g);
return 0;
}
```
上述代码中,我们使用了邻接矩阵存储图,使用Prim算法构建最小生成树。在使用Prim算法时,我们需要维护lowcost数组和closest数组,分别表示到当前生成树的最小距离和当前生成树中与其它点最近的点。在每一轮构建时,我们找到距离当前生成树最近的点,将其加入生成树,并更新lowcost和closest数组。最后输出生成树即可。