Kruskal's 算法 (最小生成树)

在本文中，我们将讨论 Kruskal's 算法。在此，我们还将讨论 Kruskal's 算法的复杂性、工作原理、示例和实现。

但在直接进入算法之前，我们应该先理解一些基本术语，如生成树和最小生成树。

生成树 - 生成树是无向连通图的子图。

最小生成树 - 最小生成树可以定义为所有边权重之和最小的生成树。生成树的权重是给生成树的边赋予的权重的总和。

现在，让我们开始讨论主要话题。

Kruskal's 算法 用于查找连通加权图的最小生成树。该算法的主要目标是找到一个边的子集，用它我们可以遍历图中的所有顶点。它遵循贪心方法，在每个阶段都寻找最优解，而不是关注全局最优。

Kruskal's 算法是如何工作的？

在 Kruskal's 算法中，我们从权重最低的边开始，并不断添加边，直到达到目标。实现 Kruskal's 算法的步骤如下：

• 首先，将所有边按权重从小到大排序。
• 然后，选择权重最低的边并将其添加到生成树中。如果将要添加的边会形成一个环，则拒绝该边。
• 继续添加边，直到我们到达所有顶点，并生成最小生成树。

Kruskal's 算法的应用包括：

• Kruskal's 算法可用于在城市之间布局电气布线。
• 它可以用于铺设 LAN 连接。

Kruskal's 算法示例

现在，让我们通过一个例子来了解 Kruskal's 算法的工作原理。通过示例更容易理解 Kruskal's 算法。

假设一个加权图是 -

上述图的边权重如下表所示：

现在，将上面给出的边按权重升序排序。

现在，让我们开始构建最小生成树。

步骤 1 - 首先，将权重为 1 的边 AB 添加到 MST 中。

步骤 2 - 将权重为 2 的边 DE 添加到 MST 中，因为它没有形成环。

步骤 3 - 将权重为 3 的边 BC 添加到 MST 中，因为它没有形成任何环路。

步骤 4 - 现在，选择权重为 4 的边 CD 添加到 MST 中，因为它没有形成环。

步骤 5 - 之后，选择权重为 5 的边 AE。包含此边将形成环，因此将其丢弃。

步骤 6 - 选择权重为 7 的边 AC。包含此边将形成环，因此将其丢弃。

步骤 7 - 选择权重为 10 的边 AD。包含此边也将形成环，因此将其丢弃。

因此，通过 Kruskal's 算法从给定的加权图中获得的最终最小生成树是 -

MST 的成本为 = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10。

现在，上图中的边数等于顶点数减一。所以，算法在这里停止。

算法

Kruskal's 算法的复杂性

现在，让我们看一下 Kruskal's 算法的时间复杂度。

• 时间复杂度
  Kruskal's 算法的时间复杂度为 O(E logE) 或 O(V logV)，其中 E 是边的数量，V 是顶点的数量。

Kruskal's 算法的实现

现在，让我们看一下 kruskal's 算法的实现。

程序：编写一个 C++ 程序来实现 kruskal's 算法。

输出

所以，这就是关于本文的全部内容。希望本文能对您有所帮助并提供信息。