用C语言实现Kruskal算法

以下是使用C语言实现Kruskal算法的代码：

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

#define MAX_VERTICES 100 // 最大顶点数
#define MAX_EDGES 100 // 最大边数

// 边的结构体
typedef struct {
    int u, v; // 边的两个顶点
    int weight; // 边的权重
} Edge;

// 图的结构体
typedef struct {
    int n; // 顶点数
    Edge edges[MAX_EDGES]; // 边的数组
} Graph;

// 初始化图
void initGraph(Graph *g, int n) {
    g->n = n;
}

// 添加边
void addEdge(Graph *g, int u, int v, int w) {
    g->edges[g->n].u = u;
    g->edges[g->n].v = v;
    g->edges[g->n].weight = w;
    g->n++;
}

// 快速排序
void quickSort(Edge *edges, int start, int end) {
    if (start >= end) return;
    int pivot = start, i = start, j = end;
    while (i < j) {
        while (i < j && edges[i].weight <= edges[pivot].weight) i++;
        while (i < j && edges[j].weight > edges[pivot].weight) j--;
        if (i < j) {
            Edge temp = edges[i];
            edges[i] = edges[j];
            edges[j] = temp;
        }
    }
    Edge temp = edges[pivot];
    edges[pivot] = edges[j];
    edges[j] = temp;
    quickSort(edges, start, j - 1);
    quickSort(edges, j + 1, end);
}

// 查找顶点所在的集合
int findSet(int *parent, int v) {
    while (v != parent[v]) {
        v = parent[v];
    }
    return v;
}

// 合并两个集合
void unionSet(int *parent, int *rank, int u, int v) {
    if (rank[u] > rank[v]) {
        parent[v] = u;
    } else if (rank[u] < rank[v]) {
        parent[u] = v;
    } else {
        parent[u] = v;
        rank[v]++;
    }
}

// Kruskal算法
void kruskal(Graph *g) {
    int parent[MAX_VERTICES], rank[MAX_VERTICES];
    int i, j, u, v, totalWeight = 0;
    Edge selectedEdges[MAX_VERTICES];
    for (i = 0; i < g->n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    quickSort(g->edges, 0, g->n - 1); // 将边按权值从小到大排序
    j = 0;
    for (i = 0; i < g->n; i++) {
        u = g->edges[i].u;
        v = g->edges[i].v;
        if (findSet(parent, u) != findSet(parent, v)) { // 判断是否在同一个集合中
            unionSet(parent, rank, findSet(parent, u), findSet(parent, v)); // 合并两个集合
            selectedEdges[j++] = g->edges[i]; // 添加选中的边
            totalWeight += g->edges[i].weight; // 计算总权重
        }
    }
    // 输出选中的边和总权重
    printf("选中的边：\n");
    for (i = 0; i < j; i++) {
        printf("(%d, %d) ", selectedEdges[i].u, selectedEdges[i].v);
    }
    printf("\n总权重：%d\n", totalWeight);
}

int main() {
    Graph g;
    int i, j, n;
    printf("请输入顶点数：");
    scanf("%d", &n);
    initGraph(&g, n);
    printf("请输入边数：");
    scanf("%d", &i);
    printf("请输入每条边的两个顶点和权重：\n");
    while (i--) {
        scanf("%d%d%d", &j, &n, &(g.edges[g.n].weight));
        addEdge(&g, j, n, g.edges[g.n].weight);
    }
    kruskal(&g);
    return 0;
}

Kruskal算法的基本思路是按照边的权值从小到大依次加入图中，如果加入的边不会形成环，则选择该边，直到选中了n-1条边为止，这n-1条边就构成了最小生成树。在程序中，我们使用邻接表来表示图，使用快速排序将边按权值从小到大排序，使用并查集来判断是否形成环。首先将每个顶点初始化为一个独立的集合，然后按照边的权值从小到大依次处理每个边，如果边的两个顶点不在同一个集合中，则将它们合并成一个集合，并将该边加入选中的边的数组中。重复这个过程，直到选中了n-1条边为止，最后输出选中的边和总权重。