Kruskals 算法的时间复杂度

在本篇文章中，我们将讨论 Kruskal 算法。我们还将在这里研究 Kruskal 算法的难度、功能、示例和实现。

然而，在继续讨论该技术之前，我们需要首先理解基本概念，例如生成树和最小生成树。

Kruskal 算法通过查找无向边加权图的最小生成森林来找到它。如果图已连接，则查找最小生成树。（最小生成树是一组边，它构成一个树，其中连通图中的每个顶点都在其中，并且树中所有边的加权平均值最小。不连通图的最小生成森林由每个连通分量的最小生成树组成。）在图论中，它被称为贪婪方法，因为它不断添加下一个不会构成循环的最低权重边到最小生成森林中。

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

最小生成树 - 最小生成树是总边权重最低的树。生成树的权重是其边所分配权重的总和。

现在让我们谈谈重点。

对于连通加权图，Kruskal 算法用于确定最小生成树。该算法的主要目标是识别边的子集，这将使我们能够遍历每个图顶点。它不关注全局最优，而是采用贪婪策略，在每一步中寻求最佳结果。

Kruskal 算法如何实现？

使用 Kruskal 方法，我们从权重最低的边开始，并不断添加边，直到获得所需的结果。以下是应用 Kruskal 算法的步骤：

• 首先将所有边按从低到高的权重排序。
• 此时，将权重最轻的边添加到生成树中。如果它会导致循环，则拒绝该边。
• 一旦我们包含了所有边，就会生成一个最小生成树。

Kruskal 算法的用途包括：

• 城市之间的布线可以使用 Kruskal 方法进行布置。
• 它可以用于安装 LAN 连接。

Kruskal 算法示例

现在让我们通过一个例子来演示 Kruskal 算法的工作原理。一个插图将使理解 Kruskal 算法更容易。

假设一个加权图是

下表提供了上述图的边权重。

现在根据升序权重对上面列出的边进行排序。

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

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

步骤 2： 由于权重为 2 的边 DE 没有产生循环，因此将其添加到 MST 中。

步骤 3： 在步骤 3 中将权重为 3 的边 BC 添加到 MST 中，因为它不产生循环。

步骤 4： 此时选择权重为 4 的边 CD 添加到 MST 中，因为没有形成循环。

步骤 5： 接下来，选择边 AE 上权重为 5 的边。必须消除此边，因为包含它会开始循环。

步骤 6： 在步骤 6 中使用权重选择 AC 边。必须消除此边，因为包含它会开始循环。

步骤 7： 在步骤 7 中选择权重为 10 的边 AD。丢弃此边将阻止循环的开始。

步骤 8： 因此，使用 Kruskal 方法从给定加权图创建的最终最小生成树是：

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

在上述树中，边的数量现在与顶点的数量减 1 相匹配。因此算法在此结束。

Kruskal 算法的时间复杂度

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

一个连接的无向图，包含其所有顶点，被称为生成树，它是图的树状子图。或者，用外行的话说，它是图边的一个子集，它们共同形成一个无环树，图的所有节点都是其成员。

最小生成树具有生成树的所有特性，并附加了所有可能的生成树中权重最低的限制。与生成树类似，一个图可能存在多个可能的 MST。

生成树的属性

生成树遵循以下原则：

• 图和生成树都具有相同数量的顶点 (V)。
• 生成树的边数是固定的，比顶点总数少一 (E = V-1)。
• 应该只有一个分量源，而不是更多，这样生成树就不会断开连接。
• 生成树中不应该有循环，这意味着它应该是无环的。
• 所有生成树的边权重之和称为生成树的总成本（或权重）。
• 一个图可以使用多个生成树。

Kruskal 算法的实现

现在让我们检查 Kruskal 方法是如何付诸实施的。

创建一个实现 Kruskal 算法的 C++ 程序。

代码

输出

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19

时间复杂度： O (E*logE) 或 O (E*logV)

• 排序边需要 O (E * logE) 时间。
• 排序后，使用查找-并集方法迭代遍历所有边。查找和并集过程的最大时间为 O (logV)。
• O (E * logE + E * logV) 时间是总复杂度的度量。
• 由于 E 的值最多为 O (V2)，因此 O (logV) 和 O (logE) 是相同的。
• 因此，O (E* logE) 或 O (E*logV) 是通用时间复杂度。

辅助空间： O (V + E)，其中 V 是图中边的总数，E 是顶点的总数。