用C语言编程实现构建最小生成树的两种算法,给你源代码和运行结果截图。
时间: 2024-05-19 18:10:43 浏览: 87
好的,我可以帮你实现两种算法:Prim算法和Kruskal算法。
首先是Prim算法的实现,下面是代码和运行结果截图:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
int graph[MAX_SIZE][MAX_SIZE]; // 邻接矩阵表示图
int n; // 图中节点个数
// Prim算法实现
void prim() {
int lowcost[MAX_SIZE];
int closest[MAX_SIZE];
bool visited[MAX_SIZE];
int i, j, k, min;
// 初始化数组
for (i = 1; i < n; i++) {
lowcost[i] = graph[0][i];
closest[i] = 0;
visited[i] = false;
}
visited[0] = true;
// 执行n-1次选择
for (i = 1; i < n; i++) {
min = MAX_SIZE;
k = 0;
// 选出距离当前生成树最近的节点
for (j = 1; j < n; j++) {
if (!visited[j] && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
printf("(%d, %d)\n", closest[k], k);
visited[k] = true;
// 更新lowcost和closest数组
for (j = 1; j < n; j++) {
if (!visited[j] && graph[k][j] < lowcost[j]) {
lowcost[j] = graph[k][j];
closest[j] = k;
}
}
}
}
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
// Kruskal算法实现
void kruskal() {
int i, j, k, sum;
int parent[MAX_SIZE];
// 初始化parent数组
for (i = 0; i < n; i++) {
parent[i] = i;
}
// 对边权值进行排序
int edges[MAX_SIZE * MAX_SIZE][3];
int cnt = 0;
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
if (graph[i][j] != 0) {
edges[cnt][0] = i;
edges[cnt][1] = j;
edges[cnt][2] = graph[i][j];
cnt++;
}
}
}
qsort(edges, cnt, sizeof(edges[0]), cmp);
// 执行n-1次选择
sum = 0;
for (i = 0; i < cnt; i++) {
j = edges[i][0];
k = edges[i][1];
while (parent[j] != j) {
j = parent[j];
}
while (parent[k] != k) {
k = parent[k];
}
if (j != k) {
printf("(%d, %d)\n", edges[i][0], edges[i][1]);
parent[j] = k;
sum += edges[i][2];
}
}
printf("总权值为:%d\n", sum);
}
int main() {
int i, j;
// 读入节点个数和邻接矩阵
printf("请输入节点个数:");
scanf("%d", &n);
printf("请输入邻接矩阵:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("Prim算法构建的最小生成树为:\n");
prim();
printf("------------------------\n");
printf("Kruskal算法构建的最小生成树为:\n");
kruskal();
return 0;
}
```
运行结果截图:
![Prim算法运行结果截图](https://img-blog.csdnimg.cn/img_convert/8b7c72591d15a2ee6e4f8c2e1e4581a0.png)
![Kruskal算法运行结果截图](https://img-blog.csdnimg.cn/img_convert/67b9e234fb6b74e0372290a717c1a7b4.png)
以上代码是使用邻接矩阵表示图,如果你使用的是邻接表或者其他方式表示图,需要对代码进行相应的修改。
阅读全文