最小生成树问题c语言
时间: 2023-12-21 19:29:37 浏览: 18
以下是使用C语言实现最小生成树问题的Kruskal算法的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
#define MAX_EDGES 100
typedef struct {
int u, v, weight;
} Edge;
typedef struct {
int parent;
int rank;
} Subset;
int V, E;
Edge edges[MAX_EDGES];
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 KruskalMST() {
Edge result[V];
int e = 0;
int i = 0;
qsort(edges, E, sizeof(Edge), compare);
Subset subsets[V];
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 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) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
printf("Edges in MST:\n");
for (i = 0; i < e; i++) {
printf("%d - %d : %d\n", result[i].u, result[i].v, result[i].weight);
}
}
int main() {
printf("Enter the number of vertices: ");
scanf("%d", &V);
printf("Enter the number of edges: ");
scanf("%d", &E);
printf("Enter the edges (u, v, weight):\n");
for (int i = 0; i < E; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
}
KruskalMST();
return 0;
}
```