图解Kruskal算法：C语言实现及代码详解

这篇文章将带你学习图论中的经典算法之一——Kruskal算法。该算法用于寻找一个图的最小生成树，即连接所有节点且边权总和最小的树。

什么是最小生成树？

在介绍Kruskal算法之前，我们先来了解一下什么是最小生成树。假设我们有一个连通图，图中包含多个节点和连接这些节点的边，每条边都有一个权值。最小生成树就是从这个图中找到一个连接所有节点的树，且该树所有边的权值之和最小。

Kruskal算法原理

Kruskal算法的核心思想是贪心算法。它的步骤如下：

**将图中的所有边按照权值从小到大排序。**2. 初始化并查集。 并查集是一种数据结构，用于判断图中的节点是否属于同一个连通分量。初始化时，每个节点都属于一个独立的连通分量。3. 遍历排序后的边，依次判断每条边是否可以加入最小生成树。 判断的依据是边的两个端点是否属于同一个连通分量： - 如果不属于同一个连通分量，则将这条边加入最小生成树，并将两个端点所在的连通分量合并。 - 如果属于同一个连通分量，则加入这条边会形成环路，因此不能加入最小生成树。4. 重复步骤3，直到所有节点都属于同一个连通分量，或者已经遍历完所有边。

C语言代码实现

以下是Kruskal算法的C语言代码实现：c#include <stdio.h>#include <stdlib.h>

#define MAX_VERTEX_NUM 100#define MAX_EDGE_NUM 500

// 边结构体typedef struct Edge { int tail; // 边的起点 int head; // 边的终点 int weight; // 边的权值} Edge;

// 图结构体typedef struct Graph { int vertexNum; // 顶点数量 int edgeNum; // 边数量 Edge edges[MAX_EDGE_NUM]; // 边的数组} Graph;

// 并查集结构体typedef struct UnionFindSet { int father[MAX_VERTEX_NUM]; // 存储每个节点的父节点 int rank[MAX_VERTEX_NUM]; // 存储每个节点的秩，用于优化路径压缩} UnionFindSet;

// 初始化并查集void MakeSet(UnionFindSet *set, int n) { for (int i = 0; i < n; i++) { set->father[i] = i; // 初始时，每个节点的父节点是自身 set->rank[i] = 0; // 初始时，每个节点的秩为0 }}

// 查找节点所属的集合（根节点）int Find(UnionFindSet *set, int x) { if (set->father[x] != x) { // 路径压缩：将查找路径上的所有节点的父节点都指向根节点 set->father[x] = Find(set, set->father[x]); } return set->father[x];}

// 合并两个节点所属的集合void Union(UnionFindSet *set, int x, int y) { int rootX = Find(set, x); int rootY = Find(set, y); if (rootX != rootY) { // 按秩合并：将秩小的树根作为秩大的树根的子节点 if (set->rank[rootX] < set->rank[rootY]) { set->father[rootX] = rootY; } else if (set->rank[rootX] > set->rank[rootY]) { set->father[rootY] = rootX; } else { set->father[rootX] = rootY; set->rank[rootY]++; } }}

// 比较函数，用于qsort排序int cmp(const void *a, const void *b) { return ((Edge *)a)->weight - ((Edge *)b)->weight;}

// Kruskal算法void Kruskal(Graph *graph) { // 按权值从小到大排序 qsort(graph->edges, graph->edgeNum, sizeof(Edge), cmp);

// 初始化并查集    UnionFindSet set;    MakeSet(&set, graph->vertexNum);

// 记录删除的边    Edge removedEdges[MAX_EDGE_NUM];    int removedEdgeNum = 0;

// 遍历所有边    for (int i = 0; i < graph->edgeNum; i++) {        Edge e = graph->edges[i];        // 如果边的两个端点不在同一个集合中，说明不会形成环，可以加入最小生成树中        if (Find(&set, e.tail) != Find(&set, e.head)) {            Union(&set, e.tail, e.head);            printf('边 (%d, %d) 权值为 %d 加入最小生成树

', e.tail, e.head, e.weight); } else { // 否则，删除边 removedEdges[removedEdgeNum++] = e; } }}

int main() { // 构造图 Graph graph = { .vertexNum = 6, .edgeNum = 9, .edges = { {0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 7}, {3, 4, 3}, {3, 5, 6}, {4, 5, 9} } };

// 执行Kruskal算法    Kruskal(&graph);

return 0