克鲁斯卡尔生成树算法

另一种常用的最小生成树算法是 Kruskal 算法。它与 Prim 算法类似，使用贪婪的方法来寻找解决方案。下面是我们实现 Kruskal 算法所需的步骤：

  1. 创建森林 T（一组树），图中的每个顶点都是一棵独立的树。

  2. 创建一个包含图中所有边的集合 S。

  3. 当 S 不为空且 T 尚未跨度时：

    • 从 S 中删除一条权重最小的边。

    • 如果这条边连接了两棵不同的树，则将其添加到森林中，将两棵树合并为一棵树；否则，丢弃这条边。

我们将使用与普里姆算法相同的图形。下面是 Kruskal 算法的实现：

Unresolved include directive in modules/ROOT/pages/ch09/ch9-10.adoc - include::example$Chapter09/8.php[]

正如我们所看到的，我们有两个独立的函数-- unionSet 和 findSet--来执行两个不相交集合的联合操作，以及查找一个数字是否存在于一个集合中。现在，让我们用构建的图形运行程序：

Unresolved include directive in modules/ROOT/pages/ch09/ch9-10.adoc - include::example$Chapter09/8.php[]

这将产生以下输出结果，与 Prim 算法的输出结果类似：

From 2 to 0 cost is 1
From 5 to 3 cost is 2
From 1 to 0 cost is 3
From 4 to 1 cost is 3
From 5 to 2 cost is 4
Minimum cost: 13

Kruskal 算法的复杂度为 \$O (E log V)\$，优于 Prim 算法的通用实现。

总结

在本章中，我们讨论了不同的图形算法及其操作。图在解决各种问题时非常方便。我们已经看到，对于相同的图，我们可以应用不同的算法，并获得不同的性能。我们必须根据问题的性质谨慎选择要应用的算法。由于某些限制，我们在本书中忽略了许多其他图主题。还有一些主题，如图着色、双方格匹配和流问题，我们应该在适当的地方加以研究和应用。在下一章中，我们将把重点转移到本书的最后一个数据结构主题—​堆，并学习堆数据结构的不同用法。