C 语言 Kruskal 算法

在本课程中，你将了解 Kruskal 算法的运作方式。此外，你还可以找到 Python、Java、C 和 C++ 中 Kruskal 算法的运行示例。

当给定一个图作为输入时，Kruskal 算法（一种最小生成树算法）确定其边的子集，这些边

• 从图中创建一个具有最少权重的树
• 在所有可能的树中添加到每个顶点。

Kruskal 算法如何运作？

它属于一类称为贪心算法的算法，这些算法通过寻找局部最优解来找到全局最优解。

我们从权重最低的边开始，然后不断添加边，直到达到目的地。

以下是应用 Kruskal 算法的步骤：

• 按从轻到重的顺序排列每条边。
• 将权重最低的边添加到生成树中。如果添加该边会导致循环，则拒绝该边。
• 持续添加边，直到覆盖所有顶点。

Kruskal 算法伪代码

任何最小生成树算法都围绕着确定添加一条边是否会创建循环。Union Find 算法是发现此信息最常用的方法。借助 Union-Find 方法，我们可以将顶点分组，确定两个顶点是否属于同一组，并确定添加一条边是否会导致循环。

让我们看看 C 语言中 Kruskal 算法的例子

输出

2 - 1 : 2
5 - 2 : 2
3 - 2 : 3
4 - 3 : 3
1 - 0 : 4
Spanning tree cost: 14
--------------------------------
Process exited after 0.02407 seconds with return value 0
Press any key to continue . . .

Prim 算法与 Kruskal 算法

另一种流行的最小生成树方法是 Prim 算法，它采用不同的逻辑来确定图的 MST。Prim 算法从一个顶点开始，而不是一条边，并不断添加不属于树的最低权重边，直到覆盖所有顶点。