kruskal求最小生成树c语言
时间: 2024-05-05 14:12:19 浏览: 102
kruskal求最小生成树
4星 · 用户满意度95%
以下是Kruskal算法求最小生成树的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
#define MAX_EDGES 10000
typedef struct {
int u, v, weight;
} edge;
typedef struct {
int parent;
int rank;
} subset;
int V, E;
edge edges[MAX_EDGES];
subset subsets[MAX_VERTICES];
int find(subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
void Union(subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
int compare(const void* a, const void* b) {
edge* a1 = (edge*)a;
edge* b1 = (edge*)b;
return a1->weight > b1->weight;
}
void kruskal() {
int i, j;
int e = 0;
int total_weight = 0;
qsort(edges, E, sizeof(edge), compare);
for (i = 0; i < V; i++) {
subsets[i].parent = i;
subsets[i].rank = 0;
}
i = 0;
while (e < V - 1 && i < E) {
edge next_edge = edges[i++];
int x = find(subsets, next_edge.u);
int y = find(subsets, next_edge.v);
if (x != y) {
Union(subsets, x, y);
printf("%d - %d: %d\n", next_edge.u, next_edge.v, next_edge.weight);
total_weight += next_edge.weight;
e++;
}
}
printf("Total weight of MST: %d\n", total_weight);
}
int main() {
int i;
scanf("%d %d", &V, &E);
for (i = 0; i < E; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
}
kruskal();
return 0;
}
```
阅读全文