c语言代码实现克鲁斯卡尔最小生成树

以下是使用C语言实现克鲁斯卡尔最小生成树的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100
#define MAX_EDGES MAX_VERTICES * (MAX_VERTICES - 1) / 2

typedef struct {
    int start, end, weight;
} Edge;

typedef struct {
    int parent;
    int rank;
} Subset;

typedef struct {
    Edge edges[MAX_EDGES];
    int num_edges;
} Graph;

Graph create_graph(int num_vertices, int num_edges)
{
    Graph graph;
    graph.num_edges = num_edges;

    for (int i = 0; i < num_edges; i++) {
        printf("Enter start, end and weight of edge %d: ", i + 1);
        scanf("%d %d %d", &graph.edges[i].start, &graph.edges[i].end, &graph.edges[i].weight);
    }

    return graph;
}

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_sets(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_edges(const void* a, const void* b)
{
    Edge* edge1 = (Edge*)a;
    Edge* edge2 = (Edge*)b;

    return edge1->weight - edge2->weight;
}

void kruskal_mst(Graph graph, int num_vertices)
{
    Edge result[num_vertices];
    int e = 0;
    int i = 0;
    Subset subsets[num_vertices];

    for (int v = 0; v < num_vertices; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    qsort(graph.edges, graph.num_edges, sizeof(graph.edges[0]), compare_edges);

    while (e < num_vertices - 1 && i < graph.num_edges) {
        Edge next_edge = graph.edges[i++];

        int x = find(subsets, next_edge.start);
        int y = find(subsets, next_edge.end);

        if (x != y) {
            result[e++] = next_edge;
            union_sets(subsets, x, y);
        }
    }

    printf("Minimum spanning tree:\n");

    for (i = 0; i < e; i++) {
        printf("%d - %d: %d\n", result[i].start, result[i].end, result[i].weight);
    }
}

int main()
{
    int num_vertices, num_edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &num_vertices);
    num_edges = num_vertices * (num_vertices - 1) / 2;
    Graph graph = create_graph(num_vertices, num_edges);
    kruskal_mst(graph, num_vertices);
    return 0;
}

在这个实现中，我们使用了一个结构体来表示每条边，其中包括起点、终点和权重。我们还使用了一个结构体来表示每个子集，其中包括父节点和秩。我们通过调用 `create_graph` 函数来创建图，其中我们提示用户输入每条边的起点、终点和权重。我们使用 `qsort` 函数对边按权重排序，然后使用 `kruskal_mst` 函数来计算最小生成树。在 `kruskal_mst` 函数中，我们使用一个数组来存储最小生成树的边。我们遍历每条边，将它们加入最小生成树中，同时使用并查集来避免形成环。最后，我们输出最小生成树的边。