最小生成树算法

距离我的资格考试只有十天的路程，我决定放弃教科书，改回写作。毕竟，如果我可以解释这些概念，那么我应该能够通过对它们的测试，对吗？好吧，今天我很有趣地介绍了算法课程中的一个概念：最小生成树。

最小生成树概述

在讨论最小生成树之前，我们需要讨论图。特别地，无向图是其边缘没有特定方向的图。换句话说，它是一个具有沿两个方向连接两个节点的边的图：

如果我们要以特殊方式遍历无向图，则可以构造一棵称为生成树的树。更具体地说， 生成树是图的子集，其中包含所有顶点而没有任何循环。作为附加标准，生成树必须覆盖最少数量的边：

但是，如果要将边缘权重添加到无向图，则针对最小边缘数优化树可能不会为我们提供最小生成树。特别是， 最小生成树是无向加权图的子集，其中包含所有没有任何循环的顶点。再次，生成的树必须具有最低的总边缘成本：

最后一点：最小生成树可能不是唯一的。换句话说，给定图可能有多个最小生成树。例如，如果边缘ED的成本为4，我们可以选择ED或BD来完成我们的树。

顺便说一句，让我们谈谈本文其余部分的情况。特别是，我们将研究构造最小生成树的两种算法：Prim算法和Kruskal算法。

如前所述，本文的目的是研究两种主要的最小生成树算法。两种算法都采用贪婪的方法来解决最小生成树问题，但是它们的处理方式略有不同。

构造最小生成树的一种方法是选择一个起始节点，然后将最便宜的相邻边缘不断添加到树中（避免循环），直到每个节点都已连接为止。本质上，这就是Prim的算法的工作原理。

在此示例中，我们从A开始并不断扩展树，直到连接了所有节点。在这种情况下，我们选择AB，然后选择BC，然后选择CD。最后，我们得到了成本为12的最小生成树。

当然，我们本来可以总是从任何其他节点开始以同一棵树结束。例如，我们可以从D开始，这将在另一个方向上构建树（DC-> CB-> BA）。

可以想象，这是一个非常简单的贪婪算法，总是构造最小生成树。当然，需要一些决策来避免产生周期。也就是说，只要新边缘不连接当前树中的两个节点，就不会有任何问题。

构造最小生成树的另一种方法是在所有可用边（避免循环）中连续选择最小的可用边，直到每个节点都已连接。自然，这就是Kruskal算法的工作原理。

在此示例中，我们从选择最小边沿开始，在这种情况下为AC。为了识别这种联系，我们将A和C放在一个集合中。然后，我们找到下一个最小边缘AB。在这种情况下，B尚未包含在包含A的集合中，因此我们可以安全地添加它。

在这一点上，我们遇到了一个问题。如果选择BC，则将创建一个循环，因为B和C已通过A连接。由于B和C位于同一集合中，因此我们可以安全地跳过该边。

最后，我们考虑下一个最小的边缘，即CD。由于D没有以某种方式连接到C，我们可以将其添加到包含A，B和C的集合中。由于我们的集合现在包含所有四个顶点，因此可以停止。

不幸的是，这个例子可能不是最好的，因为如果我们从A或C开始，Prim的算法将以类似的方式运行。当然，绘制这些示例会花费一些时间，因此我建议同时查阅Wikipedia的Prim和Kruskal的算法。每个页面都有一个漂亮的动画，显示了差异。

就我个人而言，我发现该算法在处理方面更具挑战性，因为我发现回避周期标准不太明显。就是说，正如我在各种教科书中所看到的那样，该解决方案通常依赖于维护代表不同树的集合中节点的集合。然后，该算法仅在两个节点位于不同树中时才选择它们。否则，在节点之间绘制一条边将创建一个循环。

翻译自: https://www.javacodegeeks.com/2019/09/minimum-spanning-tree-algorithms.html