C语言实现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;

}

// 代码讲解本代码实现了基于破圈法的Kruskal算法，用于求解无向连通图的最小生成树。

首先定义了边的结构体，包含起点、终点和权重三个属性。然后定义了存储每个节点的父节点的数组parent和存储图的所有边的数组edges，以及边的数量edgeCount。

接着实现了find函数，用于查找节点的根节点。该函数通过循环找到节点的父节点，直到找到根节点为止。

再实现unionSet函数，用于合并两个节点所在的树。该函数将一个节点的父节点指向另一个节点，从而将两个树合并成一棵树。

然后实现了sortEdges函数，用于按边的权重从大到小排序所有的边。该函数使用冒泡排序算法，对所有边进行排序。

接着实现了kruskal函数，用于执行Kruskal算法求最小生成树。该函数首先将每个节点的父节点初始化为-1，然后按边的权重从大到小排序所有的边。接着循环处理每条边，如果两个节点不在同一个圈中，则合并两个圈，并输出加入最小生成树的边。

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

整个程序的核心就是kruskal函数，该函数通过不断合并圈的方式，求解出最小生成树。整个算法的时间复杂度为O(ElogE)，其中E为边的数量。