c语言按Kruskal算法得到的最小生成树

Kruskal算法是一种用于求解连通网的最小生成树的方法，适用于边稀疏的网。下面是使用C语言实现Kruskal算法得到最小生成树的示例代码：

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

#define MAX_VERTICES 100
#define MAX_EDGES 100

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

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

typedef struct {
    int numVertices;
    int numEdges;
    Edge edges[MAX_EDGES];
} 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 unionSet(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* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}

void kruskalMST(Graph* graph) {
    int numVertices = graph->numVertices;
    Edge result[numVertices];
    int e = 0;
    int i = 0;

    qsort(graph->edges, graph->numEdges, sizeof(Edge), compare);

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

    while (e < numVertices - 1 && i < graph->numEdges) {
        Edge nextEdge = graph->edges[i++];

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

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

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

int main() {
    Graph graph;
    graph.numVertices = 4;
    graph.numEdges = 5;

    graph.edges[0].start = 0;
    graph.edges[0].end = 1;
    graph.edges[0].weight = 10;

    graph.edges[1].start = 0;
    graph.edges[1].end = 2;
    graph.edges[1].weight = 6;

    graph.edges[2].start = 0;
    graph.edges[2].end = 3;
    graph.edges[2].weight = 5;

    graph.edges[3].start = 1;
    graph.edges[3].end = 3;
    graph.edges[3].weight = 15;

    graph.edges[4].start = 2;
    graph.edges[4].end = 3;
    graph.edges[4].weight = 4;

    kruskalMST(&graph);

    return 0;
}

这段代码实现了Kruskal算法来求解连通网的最小生成树。它首先对边按照权重进行排序，然后使用并查集来判断是否形成环路，并将不形成环路的边加入最小生成树中。最后，打印出最小生成树的边及其权重。