Kruskal 算法求最小生成树：C 语言实现及详解

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

#define MAX_VERTEX_NUM 100 // 最大顶点数 #define MAX_EDGE_NUM 1000 // 最大边数

// 边的结构体 typedef struct { int start; // 起点 int end; // 终点 int weight; // 权重 } Edge;

int parent[MAX_VERTEX_NUM]; // 存储每个节点的父节点 Edge edges[MAX_EDGE_NUM]; // 存储图的所有边 int edgeCount = 0; // 边的数量

// 查找节点的根节点 int find(int node) { while (parent[node] != -1) { node = parent[node]; } return node; }

// 合并两个节点所在的树 void unionSet(int root1, int root2) { parent[root1] = root2; }

// 按权重从大到小排序 void sortEdges() { for (int i = 0; i < edgeCount - 1; i++) { for (int j = 0; j < edgeCount - i - 1; j++) { if (edges[j].weight < edges[j + 1].weight) { Edge temp = edges[j]; edges[j] = edges[j + 1]; edges[j + 1] = temp; } } } }

// 破圈法求最小生成树 void kruskal(int vertexCount) { for (int i = 0; i < vertexCount; i++) { parent[i] = -1; // 初始化每个节点的父节点为-1 }

sortEdges(); // 按边的权重从大到小排序

int edgeIndex = 0; // 当前处理的边的索引
int circleCount = vertexCount; // 圈的数量，初始值为顶点数

while (circleCount > 1 && edgeIndex < edgeCount) { // 直到图中没有圈或者处理完所有边
    Edge edge = edges[edgeIndex++]; // 取出当前权重最大的边

    int root1 = find(edge.start);
    int root2 = find(edge.end);

    if (root1 != root2) { // 如果两个节点不在同一个圈中
        unionSet(root1, root2); // 合并两个圈
        circleCount--; // 圈的数量减1
        printf('(%d, %d) weight=%d\n', edge.start, edge.end, edge.weight); // 输出加入最小生成树的边
    }
}

}

int main() { int vertexCount, edgeNum; printf("请输入顶点和边的数目:\n"); scanf("%d%d", &vertexCount, &edgeNum);

printf("请输入每条边的起始顶点、结束顶点和权值:\n");
for (int i = 0; i < edgeNum; i++) {
    scanf("%d%d%d", &edges[i].start, &edges[i].end, &edges[i].weight);
    edgeCount++; // 边的数量加1
}

kruskal(vertexCount); // 使用破圈法求最小生成树

return 0;

}

本文将详细讲解使用破圈法（Kruskal 算法）求最小生成树的 C 语言代码。

1. 宏定义

首先，我们使用宏定义定义了最大顶点数和最大边数。

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_EDGE_NUM 1000 // 最大边数

2. 边的结构体

接下来，我们定义了表示边的结构体 Edge，包括起点、终点和权重。

typedef struct {
    int start; // 起点
    int end; // 终点
    int weight; // 权重
} Edge;

3. 全局变量

我们定义了三个全局变量：

• parent 数组，用于存储每个节点的父节点。
• edges 数组，用于存储图的所有边。
• edgeCount 变量，用于存储边的数量。

int parent[MAX_VERTEX_NUM]; // 存储每个节点的父节点
Edge edges[MAX_EDGE_NUM]; // 存储图的所有边
int edgeCount = 0; // 边的数量

4. 查找节点的根节点

我们定义了一个 find 函数，用于查找节点的根节点。

int find(int node) {
    while (parent[node] != -1) {
        node = parent[node];
    }
    return node;
}

在该函数中，我们使用了 while 循环，不断查找当前节点的父节点，直到找到根节点为止。如果当前节点的父节点为 -1，则说明当前节点就是根节点，直接返回即可。

5. 合并两个节点所在的树

我们定义了一个 unionSet 函数，用于合并两个节点所在的树。

void unionSet(int root1, int root2) {
    parent[root1] = root2;
}

在该函数中，我们将 root1 的父节点设置为 root2，即将两个节点所在的树合并为一棵树。

6. 按权重从大到小排序

我们定义了一个 sortEdges 函数，用于按边的权重从大到小排序。

void sortEdges() {
    for (int i = 0; i < edgeCount - 1; i++) {
        for (int j = 0; j < edgeCount - i - 1; j++) {
            if (edges[j].weight < edges[j + 1].weight) {
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
}

在该函数中，我们使用了冒泡排序算法，将边按权重从大到小排序。

7. 破圈法求最小生成树

最后，我们定义了一个 kruskal 函数，使用破圈法求最小生成树。

void kruskal(int vertexCount) {
    for (int i = 0; i < vertexCount; i++) {
        parent[i] = -1; // 初始化每个节点的父节点为-1
    }

    sortEdges(); // 按边的权重从大到小排序

    int edgeIndex = 0; // 当前处理的边的索引
    int circleCount = vertexCount; // 圈的数量，初始值为顶点数

    while (circleCount > 1 && edgeIndex < edgeCount) { // 直到图中没有圈或者处理完所有边
        Edge edge = edges[edgeIndex++]; // 取出当前权重最大的边

        int root1 = find(edge.start);
        int root2 = find(edge.end);

        if (root1 != root2) { // 如果两个节点不在同一个圈中
            unionSet(root1, root2); // 合并两个圈
            circleCount--; // 圈的数量减1
            printf('(%d, %d) weight=%d\n', edge.start, edge.end, edge.weight); // 输出加入最小生成树的边
        }
    }
}

在该函数中，我们首先将每个节点的父节点初始化为 -1。然后按边的权重从大到小排序。接着，我们使用 while 循环，直到图中没有圈或者处理完所有边为止。在循环中，我们取出当前权重最大的边，找到该边所连接的两个节点的根节点，如果这两个节点不在同一个圈中，则将这两个圈合并为一棵树，并输出加入最小生成树的边。最后，我们将圈的数量减 1，继续处理下一条边。

8. 主函数

最后，我们在主函数中读入图的顶点和边的数目，以及每条边的起始顶点、结束顶点和权值，然后调用 kruskal 函数求最小生成树。

int main() {
    int vertexCount, edgeNum;
    printf("请输入顶点和边的数目:\n");
    scanf("%d%d", &vertexCount, &edgeNum);

    printf("请输入每条边的起始顶点、结束顶点和权值:\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d%d%d", &edges[i].start, &edges[i].end, &edges[i].weight);
        edgeCount++; // 边的数量加1
    }

    kruskal(vertexCount); // 使用破圈法求最小生成树

    return 0;
}

在该函数中，我们先读入图的顶点和边的数目，然后读入每条边的起始顶点、结束顶点和权值，将边的数量加 1。最后，我们调用 kruskal 函数求最小生成树。

完整代码如下：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_EDGE_NUM 1000 // 最大边数

// 边的结构体
typedef struct {
    int start; // 起点
    int end; // 终点
    int weight; // 权重
} Edge;

int parent[MAX_VERTEX_NUM]; // 存储每个节点的父节点
Edge edges[MAX_EDGE_NUM]; // 存储图的所有边
int edgeCount = 0; // 边的数量

// 查找节点的根节点
int find(int node) {
    while (parent[node] != -1) {
        node = parent[node];
    }
    return node;
}

// 合并两个节点所在的树
void unionSet(int root1, int root2) {
    parent[root1] = root2;
}

// 按权重从大到小排序
void sortEdges() {
    for (int i = 0; i < edgeCount - 1; i++) {
        for (int j = 0; j < edgeCount - i - 1; j++) {
            if (edges[j].weight < edges[j + 1].weight) {
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
}

// 破圈法求最小生成树
void kruskal(int vertexCount) {
    for (int i = 0; i < vertexCount; i++) {
        parent[i] = -1; // 初始化每个节点的父节点为-1
    }

    sortEdges(); // 按边的权重从大到小排序

    int edgeIndex = 0; // 当前处理的边的索引
    int circleCount = vertexCount; // 圈的数量，初始值为顶点数

    while (circleCount > 1 && edgeIndex < edgeCount) { // 直到图中没有圈或者处理完所有边
        Edge edge = edges[edgeIndex++]; // 取出当前权重最大的边

        int root1 = find(edge.start);
        int root2 = find(edge.end);

        if (root1 != root2) { // 如果两个节点不在同一个圈中
            unionSet(root1, root2); // 合并两个圈
            circleCount--; // 圈的数量减1
            printf('(%d, %d) weight=%d\n', edge.start, edge.end, edge.weight); // 输出加入最小生成树的边
        }
    }
}

int main() {
    int vertexCount, edgeNum;
    printf("请输入顶点和边的数目:\n");
    scanf("%d%d", &vertexCount, &edgeNum);

    printf("请输入每条边的起始顶点、结束顶点和权值:\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d%d%d", &edges[i].start, &edges[i].end, &edges[i].weight);
        edgeCount++; // 边的数量加1
    }

    kruskal(vertexCount); // 使用破圈法求最小生成树

    return 0;
}