Kruskal's Minimum Spanning Tree

• 下载源代码 - 21.7 KB

引言

以下文章是一个 .NET 实现 Kruskal 算法查找连通无向图最小生成树的示例。图的最小生成树是一组连接所有节点且成本最低的边。

要运行此解决方案，您需要 .NET 4.0。该示例使用 Visual Studio 10 和 WPF 进行图形表示。

背景

在本文中，我将大量使用之前用于示例 Dijkstra 算法（查找连通无向图中两个节点之间最短路径）的代码。您可以在此处找到该示例。

与 Dijkstra 算法类似，Kruskal 算法也被认为是“贪心”算法。尽管这些算法非常相似，但它们的实现方式却大不相同，因为它们的目标根本不同。在最小生成树的情况下，我们会使用一些额外的结构，这使得对算法的理解稍微困难一些。

此外，最小生成树是一个更抽象的概念，并且与实际情况的比较也稍显困难。在最短路径算法的情况下，我们将图想象成一个城市地图，其中节点代表城市，边代表连接它们的道路。我们可以为最小生成树想象一个类似的场景。例如，我们可以想象我们是一家互联网提供商，目前正在一个国家/地区建设其网络，并使用光纤连接该国的所有城市。由于光纤需要花费金钱，因此我们希望尽可能少地使用。最小生成树算法可以帮助我们做到这一点。

算法

如前所述，Kruskal 的最小生成树算法与 Dijkstra 的最短路径算法相似之处在于它们都是“贪心”算法。在寻找最短路径时，我们试图从总成本最低的节点中选择最佳的边。之所以这是一种有效的策略，是因为它减少了到达目标节点所需的访问节点数量。

为了找到最小生成树，我们需要一种略有不同的方法。为了高效地构建树，我们需要访问所有节点，同时尽可能少地访问边。因此，有必要收集图的所有边，并对它们进行排序，以便我们首先考虑成本最低的边。然而，这还不够，因为它不能保证我们只选择构建最小生成树所需的边。让我们考虑以下简单的情况。我们有一个包含三个相互连接的节点的图。我们开始收集边来构建最小生成树。我们从节点 1 和节点 2 之间的边开始。下一个合乎逻辑的选择是节点 2 和节点 3 之间的边。此时，节点 1 和节点 2 之间有直接连接，节点 2 和节点 3 之间有直接连接，并且通过节点 2，节点 1 和节点 3 之间有间接连接。因此，将最后一条边添加到最小生成树将是一个错误。

因此，最小生成树仅由节点 1 和节点 2 之间以及节点 2 和节点 3 之间的边组成。我们需要一种方法来跟踪我们已经为最小生成树选择的边以及我们已经访问过的节点。为了做到这一点，我们将使用一个我们称之为“集群”的附加结构。“集群”简单地是我们已经访问过的一组节点。当我们继续向最小生成树添加边时，我们需要检查边的每个连接节点是否已在集群中。如果两个节点都已添加，则不应将该边包含在最小生成树中，即使它是列表中的最短边。

定义了集群的角色后，就很清楚，在算法开始时，我们需要为每个节点设置一个集群。当我们继续向最小生成树添加边时，我们将不断合并集群，直到我们得到包含图中所有节点的集群。

示例

最好通过一个比前面例子更完整的例子来演示该算法。

从成本最低的边开始，我们首先将节点 2 和 5 之间的边添加到最小生成树，并首先合并节点 2 和 5 的集群。我们对节点 1 和 6 及其之间的边应用相同的逻辑。下一个应该考虑的边是节点 3 和 4 之间或节点 6 和 4 之间，因为它们的成本相同，均为 15。让我们想象一下，我们选择了节点 3 和 4 之间的边。我们发现自己处于与之前相同的情况。这些节点属于不同的集群；因此，我们以相同的方式进行。下一条是节点 4 和 6 之间的边。这些节点来自不同的集群：节点 6 与节点 1 属于同一集群，节点 4 与节点 3 属于同一集群。我们将该边添加到最小生成树，并将这两个集群合并为一个包含节点 1、6、4 和 3 的集群。此时，只剩下两个集群：我们刚刚构建的集群和包含节点 2 和 5 的集群。因此，我们选择的下一条边必须能够合并这两个集群，它将是最小生成树中的最后一条边。成本最低的边是节点 4 和 5 之间的边。这产生了总成本为 63 的最小生成树。

使用应用程序

要使用该应用程序，用户首先需要创建节点以及它们之间的边。要创建节点，用户需要单击画布。要连接两个节点，用户需要连续选择在画布上创建的两个节点。要找到最小生成树，用户需要单击“查找最小生成树”。“清除”按钮允许用户清除画布并构建新图。“重置”允许用户恢复到找到最短路径之前的图形初始状态。