Kruskal 的最小生成树算法

本质上，贪婪算法通过做出​​一系列局部最优选择来达到全局最优结果。它通过在每一步选择最佳选项来工作，而不考虑整体影响。这种机会主义的方法相当于一个在每次决策时都持续选择最容易获得的最佳选项的人，以期获得最佳的总体结果。

理解基础知识

在深入探讨树的细节之前，让我们先建立一些基本概念

• 节点：节点是树的基本组成部分。每个节点都有数据和 0 个子节点。顶部的节点称为“根”，而没有后代的节点称为“叶子”。
• 边：在树中，边将节点连接在一起。它们显示了哪些节点是父节点和子节点以及节点之间的关系。
• 层次结构：树是分层结构，这意味着它们遵循预定的层次结构。节点按层次排列，根节点位于顶部，下方有多个级别的子节点。

树的类型

存在不同类型的树，每种树都是为了实现特定功能或解决特定问题而创建的。典型的树种包括

• 二叉树： 也称为左子节点和右子节点，二叉树允许每个节点最多有两个子节点。二叉搜索树和表达式树只是二叉树众多用途中的两个示例。
• 二叉搜索树 (BST)： 二叉搜索树是一种二叉树，其中节点排列得可以快速执行搜索、插入和删除操作。父节点左侧和右侧的节点分别具有小于和大于父节点的值。
• AVL 树： AVL 树是自平衡的二叉搜索树。通过确保每个节点的左右子树高度相差不超过一，它保持了结构的平衡。这种和谐使得搜索活动有效。
• 红黑树： 另一种自平衡二叉搜索树是红黑树。它使用一组规则来保持平衡结构，使其适用于各种应用。
• B 树： B 树是多路树，常用于文件系统和数据库。通过维护具有可变数量子节点的平衡结构，它们提供了有效的数据存储和检索。
• Trie： Trie（发音为“try”）是一种类似树的数据结构，用于存储和搜索动态字符串集合，例如字典中的单词或路由器中的 IP 地址。

实际应用

既然我们已经回顾了树的基本原理和种类，现在让我们看看一些实际应用

• 文件系统：文件系统，如您计算机上的文件系统，通常使用树拓扑来组织文件和目录。每个目录都有能力容纳文件和子目录，从而形成分层结构。
• 数据库系统：为了有效存储和检索数据，许多数据库系统使用 B 树和其他树结构。即使对于大型数据集，这些结构也提供了对数据的快速访问。
• 网络路由：为了选择数据包从源到目标的最佳路由，计算机网络中的路由器使用基于树的算法。
• 编译器使用抽象语法树 (AST) 来表示程序代码的结构。AST 对于代码生成和解析至关重要。
• 组织层级结构：在公司中，组织层级结构可以表示为树，每个节点表示一个部门或员工以及它们相应的层级连接。
• 游戏开发：树用于组织游戏元素、它们的交互以及在视频游戏开发中的行为。行为树是此用途的典型示例。

总而言之，树是计算机科学和数据结构中的一个关键概念。它们在文件系统、数据库管理甚至视频游戏开发等各种应用中都至关重要，因为它们提供了管理和组织分层结构数据的有效方法。对于任何希望有效解决复杂问题的程序员或计算机科学家来说，理解各种树及其用途都非常重要。接下来的文章将更详细地介绍每种树的操作和算法。

生成树

生成树是网络分析和图论中的一个关键概念，在计算机科学、电信和交通运输等许多领域都有应用。它是图的连接子图，包含主图的所有顶点并具有树的形态。换句话说，生成树是原始图的边的子集，它保证了所有顶点之间的连接而不产生任何循环。

生成树之所以重要，原因如下

• 互联性：生成树确保网络或图中的每个节点都与其他所有节点相连。它们代表了实现不同部分或地点之间可访问性和连接能力的主干基础设施。
• 效率：生成树经常能改善资源分配和网络架构。它们在保持完全可达性的同时，最大限度地降低了网络内连接的总成本、持续时间或延迟。
• 防止环路：由于生成树是无环的，因此它们可以防止网络中形成环路或循环。为了防止数据陷入永无止境的循环，此特征对于路由算法和数据传输协议至关重要。
• 冗余：在某些应用中，为了实现冗余，网络中可能存在多个生成树。这种冗余可确保在链路发生故障时持续运行，从而提高网络的容错能力和可靠性。
• MST（最小生成树）：在图的所有潜在生成树中，最小生成树具有特殊的相关性。具有最小边权重之和的生成树是识别许多优化问题（包括网络设计和聚类）最佳解决方案的首选。

理解贪婪算法：优化选择 步步为营

贪婪算法是一种强大而合乎逻辑的方法，在计算机科学和优化领域经常脱颖而出。贪婪算法是解决问题的灵活方法，它们在每个阶段决定是最大化还是最小化某个特定的目标函数。这些算法具有简单的概念结构，但在各种应用中可能非常强大。在本帖中，我们将深入探讨贪婪算法的领域，并研究其基本原理、优点和缺点。

什么是贪婪算法？

本质上，贪婪算法通过做出​​一系列局部最优选择来达到全局最优结果。它通过在每一步选择最佳选项来工作，而不考虑整体影响。这种短视的策略相当于一个在每次决策时都持续选择最容易获得的最佳选项的人，以期获得最佳的总体结果。

贪婪算法的关键特征

1. 贪婪选择的性质

贪婪算法的“贪婪选择性质”是其关键特征。无论更广阔的图景如何，算法在每个阶段都选择在该特定时间点看起来最优的解决方案。该决策基于某个标准，该标准可能需要最大化或最小化某个特定值。

2. 最优子结构

“最优子结构”的概念是贪婪算法的基础原则，该概念指出，以最优方式解决较小的子问题将导致以最优方式解决更大的问题。换句话说，问题可以分解为更易于管理的子问题，每个子问题都可以通过采用相同的贪婪策略来解决。

使用 Kruskal 的最小生成树算法查找 MTS 的算法

1. 输入：您以加权连通图作为输入，表示为顶点和边的集合。
2. 初始化数据结构
   • 创建一个数据结构来表示图。您可以使用邻接列表或邻接矩阵。
   • 初始化一个空集合（或森林）来表示 MST。
   • 初始化一个优先队列（最小堆）来存储按权重排序的边。
3. 创建边列表：将图转换为边列表，其中每条边由一个元组（权重、顶点1、顶点2）表示。
4. 对边进行排序：按权重升序对边列表进行排序。此步骤至关重要，因为 Kruskal 算法首先选择权重最小的边。
5. 遍历边
   • 开始从最小权重到最大权重遍历排序后的边。
   • 对于每条边，检查将其添加到 MST 是否会创建循环。您可以使用不相交集并集（DSU）数据结构来高效地执行此检查。
   • 如果添加边不会创建循环（即，边的顶点尚未在森林中的同一连通分量中），则将边添加到 MST。
   • 更新 DSU 数据结构以合并边连接的两个分量。
6. 终止
   • 持续此过程，直到将 (V - 1) 条边添加到 MST，其中“V”是图中顶点的数量。对于连通图，MST 始终有 V - 1 条边。
   • 此时，您已找到最小生成树。
7. 输出：根据您的表示形式，将 MST 返回为边或顶点的集合。

以上方法的说明如下

图包含 9 个顶点和 14 条边。因此，形成的最小生成树将具有 (9 - 1) = 8 条边。

排序后

现在，从排序后的边列表中逐一选取所有边

步骤 1：选取边 7-6。未形成循环，包含它。

步骤 2：选取边 8-2。未形成循环，包含它。

步骤 3：选取边 6-5。未形成循环，包含它。

步骤 4：选取边 0-1。未形成循环，包含它。

步骤 5：选取边 2-5。未形成循环，包含它。

步骤 6：选取边 8-6。由于包含此边会形成循环，因此将其丢弃。选取边 2-3：未形成循环，包含它。

步骤 7：选取边 7-8。由于包含此边会形成循环，因此将其丢弃。选取边 0-7。未形成循环，包含它。

步骤 8：选取边 1-2。由于包含此边会形成循环，因此将其丢弃。选取边 3-4。未形成循环，包含它。

注意：由于 MST 中包含的边数等于 (V - 1)，因此算法在此停止

下面是用 C 语言实现上述方法的代码

输出

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19
.................................................................................
Process executed in 1.11 seconds
Press any key continue.

说明

1. 包含头文件：代码首先包含标准 C 函数所需的头文件
2. 比较器函数：此函数 comparator 用于根据边的权重进行比较。稍后在对边进行升序排序时使用。
3. 初始化集合：makeSet 函数初始化 parent 和 rank 数组。这些数组用于跟踪图中连接顶点的集合。
4. 查找父函数：findParent 函数用于查找给定顶点所属集合的父项（代表项）。它使用路径压缩来优化将来的查找。
5. 并集函数：unionSet 函数用于通过更新其父指针和秩来合并两个集合。
6. Kruskal 算法：kruskalAlgo 函数是 Kruskal 算法的核心。它查找给定图的 MST。
7. 对边进行排序：在运行算法之前，代码使用 qsort 函数和前面定义的 comparator 函数按权重升序对边进行排序。
8. 初始化父项和秩数组：调用 makeSet 函数来初始化父项和秩数组，将每个顶点设置为自己的父项并将秩初始化为零。
9. MST 构建：Kruskal 算法通过按权重升序迭代选择边，并在不形成循环的情况下将其添加到 MST 来构建 MST。
10. 打印 MST 边：在将边添加到 MST 时，代码会打印它们及其权重。
11. 打印最小成本：最后，代码打印 MST 的最小成本。
12. 主函数：主函数作为程序的入口点。它定义了一个边二维数组作为示例图，并调用 kruskalAlgo 来查找 MST。
13. 示例图：此代码中的示例图定义为边数组，其中每条边由三个值表示：源顶点、目标顶点和边的权重。
14. 返回 0：程序返回 0，表示成功执行。

现在用 C++ 实现

输出

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19
.................................................................................
Process executed in 1.11 seconds
Press any key continue.

说明

1. 定义了 DSU 类，它表示不相交集并集 (DSU) 数据结构。它包括构造函数和用于查找集合代表项以及执行带路径压缩和按秩合并的集合并集的方法。
2. 定义了 Graph 类，表示带权图。它包括构造函数、向图中添加边的方法以及使用 Kruskal 算法查找最小生成树 (MST) 的方法。
3. 在 main 函数中，使用四​​个顶点创建了一个 Graph 对象 g。
4. 使用 addEdge 方法将边添加到图中。
5. 在 g 对象上调用 kruskals_mst 方法来查找和显示最小生成树 (MST)。
6. 在 kruskals_mst 方法内部，边按权重升序排序。
7. 使用顶点数初始化了一个不相交集并集 (DSU) 对象 s，并将变量 ans 初始化为 0，用于存储 MST 的总权重。
8. 程序打印一条消息，指示它将显示构造的 MST 中的边。
9. 一个循环遍历排序后的边列表中的每一条边。
10. 对于每条边，它提取权重、源顶点和目标顶点。
11. 通过比较包含 x 和 y 的集合的代表项（根），检查将此边添加到 MST 是否会创建循环。
12. 如果边不创建循环，它会将边添加到 MST，更新总权重 ans，并打印该边。
13. 最后，程序打印最小生成树的总权重。
14. 程序通过返回 0 来结束，表示成功执行。

时间和空间复杂度分析

时间复杂度分析

• 初始化 DSU：在 DSU 类的构造函数中，它使用大小为“n”的两个数组 parent 和 rank 进行初始化，其中“n”是图中顶点的数量。此初始化需要 O(n) 时间。
• 对边进行排序：代码根据权重对图的边进行排序。排序操作需要 O(E * log(E)) 时间，其中“E”是图中的边数。排序是此算法中最耗时的操作。
• 遍历边：然后代码对排序后的边进行一次遍历。在每次迭代中，它对 DSU 执行查找和联合操作，由于路径压缩和秩优化，这些操作基本上是常数时间操作（摊还 O(1)）。
• Kruskal 算法的总时间复杂度由排序步骤决定，因此为 O(E * log(E))。

空间复杂度分析

• DSU 数据结构：DSU 类使用两个数组：parent 和 rank，每个数组的大小为“n”，其中“n”是图中顶点的数量。因此，DSU 类的时间复杂度为 O(n)。
• 边列表：代码维护一个 edgelist 向量来存储图的边。此向量需要 O(E) 空间，其中“E”是图中的边数。
• 其他变量：kruskals_mst 函数中使用的其他变量的空间复杂度相对于上述数据结构可以忽略不计。
• 代码的总空间复杂度为 O(n + E)，其中“n”是顶点数，“E”是图中的边数。

总之，由于排序步骤，代码的时间复杂度为 O(E * log(E))，空间复杂度为 O(n + E)。影响算法性能的最重要因素是边的数量和排序算法的效率。

贪婪算法的应用

贪婪算法应用于经济学、工程学和计算机科学等各个领域。它们在以下情况下使用

1.最短路径问题

贪婪技术，例如 Dijkstra 算法，在图论和网络路由中有效地确定两个节点之间的最短路径。程序反复选择最近的未探索节点，直到到达目标。

2. Huffman 编码

数据压缩使用 Huffman 编码使用可变长度代码加密字符。使用贪婪算法，在每个阶段合并最不常见的字符来创建 Huffman 树。

3. 分数背包问题

在这个著名的优化问题中，目标是通过选择一组具有重量和价值的物品来在有限的重量容量内最大化总价值。通过选择具有最高价值重量比的物品，贪婪算法可以提供近似答案。

贪婪算法的优点

1. 简洁性

贪婪算法的主要优点之一是它们的简单性。它们易于理解、实现和分析，使其成为解决问题并高效处理时间的优选选择。

2. 效率

贪婪算法通常具有出色的时间和空间复杂度，这使其适用于实时应用和具有大型数据集的场景。

贪婪算法的局限性

虽然贪婪算法很强大，但它们并非适用于所有问题。它们存在一些固有的局限性

1.缺乏全局最优性

贪婪算法基于局部最优做出决策，而不考虑长期后果。因此，它们可能无法始终产生全局最优解。

2.无回溯

在贪婪算法中，一旦做出选择，就无法撤销。如果早期决策后来导致次优解，则没有机制可以回溯并纠正它。

贪婪算法通过在每个阶段选择局部最优选项来快速有效地解决优化问题。尽管它们存在固有的局限性，并且可能无法始终保证全局最优解，但它们是计算机科学及其他许多领域的重要工具。知道何时以及如何使用贪婪算法是一种技能，它可以带来各种现实世界场景中优美而实用的解决方案。