使用 Kruskal 算法的最小生成树（C++）

2024 年 8 月 29 日 | 阅读 12 分钟

Kruskal 算法简介

在瞬息万变的科技和信息世界中，算法对于解决复杂问题至关重要。一个简单而有效的酷算法是Kruskal 算法。它源于图论，非常适合寻找连接图中事物的最小方法。

现在，“最小生成树”听起来可能有点花哨，但它对于设计网络、规划建筑和解决优化问题至关重要。它是指用边上的权重总和最小的方式构建一个最小的连通图。Kruskal 算法以一位名叫Joseph Kruskal 的聪明人命名，它的核心是通过每一步做出最佳选择来获得最小的整体解决方案。

在我们深入了解 Kruskal 算法的工作原理时，我们将探讨基本概念、使用方法以及它在现实生活中的应用。无论您是计算机爱好者、学生还是专业开发人员，了解 Kruskal 算法都有助于您更好地理解图及其重要性。让我们一起深入了解 Kruskal 算法在图和提高效率方面的酷炫之处和实用性！

C++ 中的实现

程序

让我们通过一个例子来用 C++ 实现最小生成树的 Kruskal 算法。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Define a structure to represent an edge
struct Edge {
 int src, dest, weight;
};

// Define a structure to represent a subset for union-find
struct Subset {
 int parent, rank;
};

// Compare function for sorting edges based on their weights
bool compareEdges(const Edge &a, const Edge &b) {
 return a.weight < b.weight;
}

// Find set of an element in union-find (with path compression)
int find(Subset subsets[], int i) {
 if (subsets[i].parent != i)
 subsets[i].parent = find(subsets, subsets[i].parent);
 return subsets[i].parent;
}

// Perform union of two subsets (by rank)
void Union(Subset subsets[], int x, int y) {
 int xroot = find(subsets, x);
 int yroot = find(subsets, y);

 if (subsets[xroot].rank < subsets[yroot].rank)
 subsets[xroot].parent = yroot;
 else if (subsets[xroot].rank > subsets[yroot].rank)
 subsets[yroot].parent = xroot;
 else {
 subsets[yroot].parent = xroot;
 subsets[xroot].rank++;
 }
}

// Kruskal's algorithm to find Minimum Spanning Tree
void Kruskal(vector<Edge> &edges, int V) {
 // Sort the edges in non-decreasing order of their weights
 sort(edges.begin(), edges.end(), compareEdges);

 // Allocate memory for creating V subsets
 Subset *subsets = new Subset[V];

 // Create V subsets with single elements
 for (int i = 0; i < V; ++i) {
 subsets[i].parent = i;
 subsets[i].rank = 0;
 }

 // Initialize result
 vector<Edge> result;

 // Number of edges to be taken is equal to V-1
 int edgeIndex = 0;
 while (result.size() < V - 1) {
 // Pick the smallest edge and increment the index for the next iteration
 Edge nextEdge = edges[edgeIndex++];

 int x = find(subsets, nextEdge.src);
 int y = find(subsets, nextEdge.dest);

 // If including this edge doesn't cause a cycle, add it to the result
 if (x != y) {
 result.push_back(nextEdge);
 Union(subsets, x, y);
 }
 }

 // Print the result
 for (const Edge &edge : result)
 cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;

 // Cleanup
 delete[] subsets;
}

int main() {
 // Example usage
 int V = 4; // Number of vertices
 vector<Edge> edges = {
 {0, 1, 10},
 {0, 2, 6},
 {0, 3, 5},
 {1, 3, 15},
 {2, 3, 4}
 };

 Kruskal(edges, V);

 return 0;
}

输出

2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

说明

1. 按权重对边进行排序

Kruskal 算法首先按照边的权重升序对图中的所有边进行排序。这对于算法采用的贪心策略至关重要。

2. 初始化子集

为图中的每个顶点创建子集。最初，每个顶点都属于自己的子集。

3. 遍历排序后的边

从最小的边开始，遍历边的排序列表。

4. 检查环

对于每条边，检查将其添加到不断增长的生成树中是否会形成环。这通过检查边的源顶点和目标顶点是否属于同一子集来完成。如果它们不属于同一子集，则表示添加此边不会形成环。

5. 合并操作

如果添加边不会形成环，则将其包含在最小生成树中。通过执行合并操作来更新子集，合并源顶点和目标顶点的子集。

6. 重复直到形成生成树

持续此过程，直到最小生成树包含V-1 条边，其中 V 是顶点的数量。此时，生成树连接了所有顶点而没有形成任何环。

7. 结果

结果是一棵连接所有顶点且总边权重最小的最小生成树。

方法 2

让我们再举一个例子，用 C++ 实现最小生成树的 Kruskal 算法。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
 int src, dest, weight;
};

// Helper class for Union-Find with path compression
class UnionFind {
public:
 vector<int> parent, rank;

 UnionFind(int size) {
 parent.resize(size);
 rank.resize(size, 0);
 for (int i = 0; i < size; ++i) {
 parent[i] = i;
 }
 }

 int find(int x) {
 if (parent[x] != x) {
 parent[x] = find(parent[x]); // Path compression
 }
 return parent[x];
 }

 void unite(int x, int y) {
 int rootX = find(x);
 int rootY = find(y);

 if (rootX != rootY) {
 if (rank[rootX] < rank[rootY]) {
 parent[rootX] = rootY;
 } else if (rank[rootX] > rank[rootY]) {
 parent[rootY] = rootX;
 } else {
 parent[rootY] = rootX;
 rank[rootX]++;
 }
 }
 }
};

bool compareEdges(const Edge &a, const Edge &b) {
 return a.weight < b.weight;
}

void kruskalMST(vector<Edge> &edges, int V) {
 sort(edges.begin(), edges.end(), compareEdges);

 UnionFind uf(V);
 vector<Edge> result;

 for (const Edge &edge : edges) {
 int rootSrc = uf.find(edge.src);
 int rootDest = uf.find(edge.dest);

 if (rootSrc != rootDest) {
 result.push_back(edge);
 uf.unite(rootSrc, rootDest);
 }
 }

 for (const Edge &edge : result) {
 cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
 }
}

int main() {
 int V = 4;
 vector<Edge> edges = {
 {0, 1, 10},
 {0, 2, 6},
 {0, 3, 5},
 {1, 3, 15},
 {2, 3, 4}
 };

 kruskalMST(edges, V);

 return 0;
}

输出

Minimum Spanning Tree:
Edge: 2 -- 3, Weight: 4
Edge: 0 -- 3, Weight: 5
Edge: 0 -- 1, Weight: 10

说明

排序边

该算法首先按权重对图中的所有边进行非递减排序。

这通常使用排序算法完成，并且排序过程是 Kruskal 算法的关键步骤。

并查集数据结构

Kruskal 算法使用一种称为并查集的数据结构来有效地检测图中的环。

它跟踪不相交集合，并允许快速检查添加边是否会形成环。

边选择

从最小的边开始，算法遍历排序后的边。

对于每条边，它使用并查集数据结构检查将其添加到不断增长的MST 中是否会形成环。

将边添加到 MST

如果添加边不会形成环，则将其添加到MST 中。

此过程一直持续到 MST 包含V-1 条边，其中 V 是图中顶点的数量。

Kruskal 算法与 Prim 算法

Kruskal 算法

策略模式

贪心： Kruskal 算法遵循贪心策略，在每一步选择最小的可用边。

边选择

与顶点无关：它独立于顶点选择边。

数据结构

并查集（Union-Find）：它通常使用并查集数据结构来有效地检查环和执行合并操作。

复杂度

边排序：它涉及按权重对所有边进行排序，这在稠密图中可能耗时。

适用性

稀疏图：它在边数远小于可能的最大值的稀疏图上通常表现良好。

并行化

由于边选择的独立性，更易于并行化。

Prim 算法

策略模式

贪心： Prim 算法也是一种贪心算法，在每一步选择最小的可用边。

边选择

依赖于起始顶点：它根据起始顶点选择边，然后从该起始点开始增长 MST。

数据结构

优先队列：它通常使用优先队列来有效地选择连接到不断增长的MST 的最小边。

复杂度

无需排序：它不需要对所有边进行排序，这使得它在稠密图中可能更有效。

适用性

稠密图：由于避免了对所有边进行排序，因此在稠密图上表现良好。

并行化

并行化受限：由于依赖于起始顶点和优先队列的需求，并行化更具挑战性。

比较概述

边排序：Kruskal 涉及对所有边进行排序，而 Prim 不需要排序。对于稠密图，Prim 在时间复杂度方面可能具有优势。
并行化：Kruskal 更容易并行化，因为边选择的过程更加独立。相比之下，Prim 由于依赖于起始顶点而更难并行化。
空间复杂度：Kruskal 由于使用了并查集数据结构，通常具有较高的空间复杂度。Prim 在某些情况下可能使用较少的内存。
起始顶点：Kruskal 不依赖于特定的起始顶点，使其实现更简单。Prim 需要选择一个起始顶点，这会影响最终的 MST。
应用：这两种算法都用于各种应用，例如网络设计，但它们之间的选择通常取决于图的特定特性和问题需求。

Kruskal 算法的优点

Kruskal 算法有几个优点。Kruskal 算法的一些主要优点如下：

简单性：Kruskal 算法相对容易理解和实现。其直接的逻辑和易于实现的特性使其易于学习和实际使用。
贪心方法：该算法通过在每一步选择最小的边来遵循贪心策略。这种局部优化策略可以得到全局最优解，从而确保高效地识别出整体最小生成树。
效率：Kruskal 算法效率很高，尤其是在与并查集（Union-Find）等数据结构结合实现时。这些结构确保了快速的环检查和高效的子集合并操作。
最优性：该算法保证了解决方案的最优性。Kruskal 算法生成的最小生成树的总边权重总是最小的，因此适用于最小化总体成本或权重至关重要的场景。
分布式计算：Kruskal 算法适用于分布式计算环境。其操作的性质，特别是处理断开连接的组件的能力，使其适用于数据和计算分布在多个节点上的场景。
通用性：Kruskal 算法不限于特定类型的图。它可以应用于稠密图和稀疏图，使其适用于各种应用。
无初始假设：与其他一些算法不同，Kruskal 算法不需要对起始点进行任何假设。它从最小的边开始，并增量地构建生成树，确保选择特定顶点作为起始点不会影响解决方案。
并行化：该算法的结构允许并行化，使其适用于在并行计算环境中实现。在某些情况下，此功能可以提高性能。

Kruskal 算法是高效解决图的最小生成树问题的强大工具，在简单性、最优性和通用性之间取得了平衡。

Kruskal 算法的应用

Kruskal 算法有几个应用。Kruskal 算法的一些主要应用如下：

网络设计：Kruskal 算法广泛用于设计通信网络，例如计算机网络、电信网络和交通网络。它有助于在节点之间建立最有效的连接，以最小化成本或最大化数据传输速率。
电路设计：在电子电路设计中，Kruskal 算法可用于最小化总线长，同时确保所有组件都已连接。这在集成电路和印刷电路板的设计中尤为重要。
城市规划：Kruskal 算法可用于城市规划，以优化道路、公用设施和基础设施的布局。它有助于创建有效地连接城市或地区不同部分的网络。
资源管理：在资源管理和分配中，Kruskal 算法通过识别最有效的路径或连接来帮助优化资源的分配。它可以应用于供水、能源传输或管道网络等场景。
无线传感器网络：在需要以最小通信开销连接传感器的无线传感器网络中，Kruskal 算法可用于建立高效的通信链路，同时最大限度地减少整体能耗。
图像分割：在图像处理中，Kruskal 算法可用于图像分割。它有助于识别图像中最重要的边或连接，从而有助于对象识别和计算机视觉等任务。
机器人技术：在机器人技术中，尤其是在路径规划和机器人代理协调方面，Kruskal 算法可用于确定多个机器人在环境中导航的最佳路径。
生物学和 DNA 测序：在计算生物学中，Kruskal 算法可用于分析生物数据，例如识别物种之间的进化关系或DNA 片段的测序。
VLSI 设计（超大规模集成）：Kruskal 算法在VLSI 设计中用于优化芯片上组件的布局。它有助于最小化总线长，减少延迟并提高整体性能。
游戏设计：Kruskal 算法可用于游戏开发中创建逼真的地形、道路网络或迷宫。它有助于生成既连通又高效的游戏环境。

这些应用突显了 Kruskal 算法在解决跨不同领域的连接和资源利用相关的优化问题方面的通用性。

Kruskal 算法的缺点

Kruskal 算法有几个缺点。Kruskal 算法的一些主要缺点如下：

在稠密图上的效率低下：当处理边数接近最大可能值的稠密图时，Kruskal 算法可能效率低下。这是因为对大量边进行排序可能耗时。
空间复杂度：该算法的空间复杂度相对较高，尤其是在使用并查集等附加数据结构时。在内存使用是关注点的情况下，这可能是一个缺点。
对断开连接的图处理不当：Kruskal 算法假设给定的图是连通的。如果图不是连通的，则需要额外的步骤或修改来处理断开连接的组件，从而使实现更加复杂。
不适用于动态图：该算法专为静态图设计，并且不能自然地适应图结构的变化。如果图是动态的，并且边频繁添加或删除，那么 Kruskal 算法可能不是最有效的选择。
等权边：如果图中存在权重相等的边，Kruskal 算法在不同的实现或排序方法下可能会产生不同的最小生成树。在某些情况下，这种缺乏唯一性可能是一个缺点。
不考虑边成本：Kruskal 算法仅考虑边的权重，而不考虑其他因素，例如添加边的成本。在某些实际应用中，添加边的成本可能不仅仅取决于其权重。
在某些情况下可能不是最优的：虽然 Kruskal 算法在边权重方面保证了最小生成树的最优性，但在需要考虑其他因素的特定实际应用中，它可能不总是能产生最优化解决方案。
不适合并行化：尽管 Kruskal 算法的某些部分可以并行化，但其整体结构本身并不适合并行处理。这可能会限制其在某些高性能计算环境中的性能。

尽管存在这些缺点，Kruskal 算法仍然是查找各种应用中最小生成树的强大且广泛使用的方法。在为特定问题或应用选择算法时，了解其局限性很重要。

结论

总之，Kruskal 算法是图论中一种重要的方法，它通过采用贪心策略来有效地解决最小生成树 (MST) 问题。它的简单性和有效性源于根据权重对边进行排序以及使用并查集数据结构进行环检测。通过迭代地选择最小的非环边，Kruskal 算法构建了一个 MST，以最小的总边权重连接所有顶点。这种通用性使其适用于网络设计、城市规划和机器人技术等各种领域。尽管其时间复杂度受到边排序的影响，但 Kruskal 算法仍然是优化各种场景中连接性的重要工具。

下一主题C++ 中的 std::is_trivially_assignable

使用 Kruskal 算法的最小生成树（C++）

Kruskal 算法简介

C++ 中的实现

方法 2

Kruskal 算法与 Prim 算法

Kruskal 算法

Prim 算法

比较概述

Kruskal 算法的优点

Kruskal 算法的应用

Kruskal 算法的缺点

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

使用 Kruskal 算法的最小生成树（C++）

Kruskal 算法简介

C++ 中的实现

方法 2

Kruskal 算法与 Prim 算法

Kruskal 算法

Prim 算法

比较概述

Kruskal 算法的优点

Kruskal 算法的应用

Kruskal 算法的缺点

结论

相关帖子

C++ 合并重叠区间

C++ 中心二十面体数程序

C++ 幂集算法

C++ ToLOWER

C++ 二叉堆

C++ Boost 库

在 C++ 中生成数组排列的不同方法

C++ 稳定婚配问题

C++ 二叉树的直径