Kruskal’s algorithm
你好,我是悦创。
Kruskal 算法是一种用于解决图的最小生成树(Minimum Spanning Tree, MST)问题的贪心算法。简单来说,最小生成树就是一个连接所有顶点的无环子图,且边的权重和最小。这个算法经常用于网络设计,比如将多个城市连接成网络,尽可能减少铺设线路的总长度。下面是 Kruskal 算法的简单步骤和每一步的详细解释。
1. Kruskal 算法的步骤
- 对边排序:将图中所有的边按权重(比如距离、费用)从小到大排序。
- 初始化一个森林:每个顶点看作一个单独的集合(森林)。
- 逐条添加边:从最小权重的边开始,依次尝试加入生成树中:
- 如果加入这条边不会形成环,就把它加入生成树。
- 如果加入这条边会形成环,就跳过它。
- 重复步骤3直到生成树中有n-1条边(n为图中顶点数)。
最终结果是包含所有顶点、权重和最小的生成树。
2. 步骤详解
2.1 第一步:对边排序
首先,将所有边按权重大小排序。这一步可以帮助我们找到最小的边。比如,假设图中有以下边:
- 边(A, B),权重3
- 边(B, C),权重1
- 边(A, C),权重2
我们会按权重大小排序得到:[(B, C), (A, C), (A, B)]。
2.2 第二步:初始化森林
假设图中有三个顶点A、B和C。我们开始时将每个顶点当作一个单独的集合,也就是说现在有三个集合{A}, {B}, {C}。
2.3 第三步:逐条添加边
选取权重最小的边(B, C),权重1。
- 检查添加这条边是否会形成环。因为B和C属于不同的集合,所以不会形成环,可以加入生成树。
- 将B和C合并到一个集合中,更新森林为{A}, {B, C}。
选取下一个最小边(A, C),权重2。
- 检查添加这条边是否会形成环。A和C属于不同的集合,所以不会形成环,可以加入生成树。
- 将A加入集合{B, C}中,更新森林为{A, B, C}。
继续选择下一条边(A, B),权重3。
- 检查添加这条边是否会形成环。A和B现在属于同一个集合{A, B, C},因此加入这条边会形成环,跳过它。
到这里,我们的最小生成树包含了边(B, C)和(A, C),权重和为3。这就是最终结果。
3. Kruskal 算法的关键概念
- 并查集(Union-Find):用于跟踪顶点属于哪个集合,并帮助检测是否形成环。这个数据结构可以让合并集合和查找集合变得快速高效。
- 贪心策略:Kruskal算法选择权重最小的边开始添加,这是贪心算法的一种特性。它保证每一步都选择当前最优的边,从而达到全局最优。
4. Kruskal 算法的复杂度
Kruskal算法的时间复杂度取决于排序和并查集的操作,通常为 ,其中 是边的数量, 是顶点的数量, 是极小的阿克曼函数,几乎可以视为常数。因此,Kruskal 算法适用于边较少的稀疏图。
总结:Kruskal 算法通过逐步添加最小权重的边来构建最小生成树,确保不会形成环。
5. 具体例子
5.1 示例图
假设我们有一个带权无向图,包含6个顶点(A, B, C, D, E, F)和9条边,边的权重如下:
边 | 权重 |
---|---|
A - B | 4 |
A - F | 2 |
B - C | 6 |
B - F | 5 |
C - D | 3 |
C - E | 7 |
D - E | 8 |
D - F | 4 |
E - F | 1 |
5.2 Kruskal 算法执行步骤
步骤1:对所有边按权重从小到大排序
我们将所有边按照权重升序排列:
- E - F,权重1
- A - F,权重2
- C - D,权重3
- A - B,权重4
- D - F,权重4
- B - F,权重5
- B - C,权重6
- C - E,权重7
- D - E,权重8
步骤2:初始化森林
每个顶点单独成为一个集合(森林中的一棵树):
- {A}, {B}, {C}, {D}, {E}, {F}
步骤3:逐条考虑边,构建最小生成树
我们依次考虑排序后的边,判断是否加入生成树。
边 E - F,权重1
- 判断:顶点E和F属于不同的集合,加入此边不会形成环。
- 行动:将边E - F加入生成树。
- 更新集合:合并集合{E}和{F}为{E, F}。
边 A - F,权重2
- 判断:顶点A和F分别属于集合{A}和{E, F},不同集合。
- 行动:将边A - F加入生成树。
- 更新集合:合并集合{A}和{E, F}为{A, E, F}。
边 C - D,权重3
- 判断:顶点C和D属于不同的集合{C}和{D}。
- 行动:将边C - D加入生成树。
- 更新集合:合并集合{C}和{D}为{C, D}。
边 A - B,权重4
- 判断:顶点A和B分别属于集合{A, E, F}和{B}。
- 行动:将边A - B加入生成树。
- 更新集合:合并集合{A, E, F}和{B}为{A, B, E, F}。
边 D - F,权重4
- 判断:顶点D(属于{C, D})和F(属于{A, B, E, F})在不同集合。
- 行动:将边D - F加入生成树。
- 更新集合:合并集合{C, D}和{A, B, E, F}为{A, B, C, D, E, F}。
停止条件
- 判断:生成树中已包含5条边(顶点数6 - 1),算法结束。
5.3 最终的最小生成树
包含的边及其权重:
- E - F,权重1
- A - F,权重2
- C - D,权重3
- A - B,权重4
- D - F,权重4
总权重:1 + 2 + 3 + 4 + 4 = 14
5.4 可视化最小生成树
4
A ----- B
|
2
|
F
/ \
1/ \4
E D
|
3
C
5.5 详细说明
跳过的边及原因:
边 B - F,权重5
- 判断:顶点B和F已在同一集合({A, B, E, F, C, D})。
- 行动:加入此边会形成环,跳过。
边 B - C,权重6
- 判断:顶点B和C已在同一集合。
- 行动:加入此边会形成环,跳过。
边 C - E,权重7
- 判断:顶点C和E已在同一集合。
- 行动:加入此边会形成环,跳过。
边 D - E,权重8
- 判断:顶点D和E已在同一集合。
- 行动:加入此边会形成环,跳过。
5.6 总结
通过上述步骤,Kruskal 算法成功构建了最小生成树,连接了所有顶点,且总权重最小(14)。该算法的核心在于:
- 贪心策略:每次选择当前权重最小的边。
- 避免环路:通过并查集检查,确保加入的边不会形成环。
5.7 关键概念回顾
并查集(Union-Find)
- 作用:快速判断两个顶点是否属于同一集合,帮助检测环的形成。
- 操作:
- 查找(Find):确定元素所属的集合。
- 合并(Union):将两个集合合并为一个。
算法复杂度
- 时间复杂度:,主要耗时在边的排序上。
6. 代码实现
# 定义边的数据结构
class Edge:
def __init__(self, u, v, weight):
self.u = u # 边的一个顶点
self.v = v # 边的另一个顶点
self.weight = weight # 边的权重
# 并查集(用于检测环)
class UnionFind:
def __init__(self, vertices):
# 初始化父节点为自己本身
self.parent = {vertex: vertex for vertex in vertices}
# 查找操作,带路径压缩
def find(self, vertex):
if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex]) # 路径压缩
return self.parent[vertex]
# 合并两个集合
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u == root_v:
return False # 合并失败,说明形成了环
self.parent[root_v] = root_u # 合并集合
return True # 合并成功
def kruskal(vertices, edges):
# 初始化并查集
uf = UnionFind(vertices)
# 将边按权重排序
sorted_edges = sorted(edges, key=lambda edge: edge.weight)
mst = [] # 最小生成树的边集合
for edge in sorted_edges:
if uf.union(edge.u, edge.v):
mst.append(edge)
# 如果边数达到 n - 1,算法结束
if len(mst) == len(vertices) - 1:
break
return mst
# 测试代码
if __name__ == "__main__":
# 定义顶点集合
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
# 定义边集合
edges = [
Edge('A', 'B', 4),
Edge('A', 'F', 2),
Edge('B', 'C', 6),
Edge('B', 'F', 5),
Edge('C', 'D', 3),
Edge('C', 'E', 7),
Edge('D', 'E', 8),
Edge('D', 'F', 4),
Edge('E', 'F', 1)
]
mst = kruskal(vertices, edges)
print("最小生成树的边为:")
total_weight = 0
for edge in mst:
print(f"{edge.u} - {edge.v}, 权重: {edge.weight}")
total_weight += edge.weight
print(f"最小生成树的总权重为:{total_weight}")
# 定义一个Edge类来表示图中的边
class Edge:
def __init__(self, u, v, weight):
self.u = u # 边的一个顶点u
self.v = v # 边的另一个顶点v
self.weight = weight # 边的权重weight
# 定义并查集类(Union-Find),用于检测环
class UnionFind:
def __init__(self, vertices):
# 初始化每个顶点的父节点为其自身,表示每个顶点都是一个独立的集合
self.parent = {vertex: vertex for vertex in vertices}
# 查找操作,找到顶点的根节点,并进行路径压缩
def find(self, vertex):
# 如果当前顶点的父节点不是自己,递归寻找父节点,直到找到根节点
if self.parent[vertex] != vertex:
# 递归调用find,路径压缩,将当前节点直接连接到根节点
self.parent[vertex] = self.find(self.parent[vertex])
# 返回根节点
return self.parent[vertex]
# 合并操作,将两个顶点所在的集合合并为一个集合
def union(self, u, v):
# 分别找到u和v的根节点
root_u = self.find(u)
root_v = self.find(v)
# 如果u和v的根节点相同,说明它们已经连通,合并会形成环,返回False
if root_u == root_v:
return False
# 否则,将v的根节点的父节点指向u的根节点,合并两个集合
self.parent[root_v] = root_u
return True # 合并成功,返回True
# Kruskal算法的主体函数
def kruskal(vertices, edges):
# 初始化并查集,传入所有顶点
uf = UnionFind(vertices)
# 将所有边按照权重从小到大排序,使用lambda函数作为排序的键
sorted_edges = sorted(edges, key=lambda edge: edge.weight)
# 初始化最小生成树的边集合为空列表
mst = []
# 遍历排序后的边集合
for edge in sorted_edges:
# 尝试将当前边的两个顶点合并
if uf.union(edge.u, edge.v):
# 如果合并成功,说明没有形成环,将该边加入最小生成树
mst.append(edge)
# 如果最小生成树的边数等于顶点数减一,生成树构建完成,退出循环
if len(mst) == len(vertices) - 1:
break
else:
# 合并失败,说明加入该边会形成环,跳过该边
continue
# 返回构建好的最小生成树的边集合
return mst
# 主程序入口,测试代码
if __name__ == "__main__":
# 定义图的顶点集合
vertices = ['A', 'B', 'C', 'D', 'E', 'F']
# 定义图的边集合,创建Edge实例,传入两个顶点和边的权重
edges = [
Edge('A', 'B', 4),
Edge('A', 'F', 2),
Edge('B', 'C', 6),
Edge('B', 'F', 5),
Edge('C', 'D', 3),
Edge('C', 'E', 7),
Edge('D', 'E', 8),
Edge('D', 'F', 4),
Edge('E', 'F', 1)
]
# 调用kruskal函数,传入顶点和边集合,获取最小生成树的边集合
mst = kruskal(vertices, edges)
# 输出最小生成树的边和总权重
print("最小生成树的边为:")
total_weight = 0 # 初始化总权重
# 遍历最小生成树的边集合
for edge in mst:
# 输出每条边的两个顶点和权重
print(f"{edge.u} - {edge.v}, 权重: {edge.weight}")
# 累加总权重
total_weight += edge.weight
# 输出最小生成树的总权重
print(f"最小生成树的总权重为:{total_weight}")
Edge类:定义了边的数据结构,包含两个顶点u
和v
以及边的权重weight
。
UnionFind类(并查集):
- 初始化:每个顶点的父节点初始化为自身,表示每个顶点都是一个独立的集合。
- find方法:查找顶点的根节点,使用了路径压缩优化,降低查找的时间复杂度。
- union方法:合并两个顶点所在的集合。如果两个顶点的根节点相同,说明它们已经在同一个集合中,合并会形成环,返回
False
;否则,将两个集合合并,返回True
。
kruskal函数:
- 初始化并查集:使用所有的顶点来初始化并查集实例。
- 边排序:将所有边按权重从小到大排序,方便后续选择最小权重的边。
- 遍历边集合:对于排序后的每一条边,尝试将其加入最小生成树:
- 使用并查集的
union
方法判断加入此边是否会形成环。 - 如果不会形成环,将边加入
mst
列表。 - 如果最小生成树的边数达到了
n - 1
(n
为顶点数),算法结束,因为最小生成树已经构建完成。
- 使用并查集的
测试代码:
- 定义顶点和边:使用之前示例中的顶点和边。
- 调用kruskal函数:计算最小生成树。
- 输出结果:打印最小生成树的边和总权重。
运行上述代码,将得到以下输出:
最小生成树的边为:
E - F, 权重: 1
A - F, 权重: 2
C - D, 权重: 3
A - B, 权重: 4
D - F, 权重: 4
最小生成树的总权重为:14
这与之前例子中的最小生成树一致。
为什么使用并查集:
- 并查集是一种高效的数据结构,用于处理不相交集合的合并和查找操作。
- 在Kruskal算法中,并查集用于检测添加一条边后是否会形成环,这对于保持生成树的无环性质至关重要。
路径压缩优化:
- 在
find
方法中,路径压缩将节点直接连接到其根节点,极大地降低了查找的时间复杂度。
- 在
时间复杂度分析:
- 边排序:(O(E \log E)),其中(E)是边的数量。
- 并查集操作:近似为(O(E \alpha(V))),(\alpha)为阿克曼函数的反函数,可以视为常数。
- 总体时间复杂度:(O(E \log E))。
如果你想将该算法应用于其他图,只需修改顶点集合和边集合即可。例如:
vertices = ['1', '2', '3', '4']
edges = [
Edge('1', '2', 1),
Edge('1', '3', 4),
Edge('2', '3', 2),
Edge('3', '4', 3)
]
通过上述 Python 实现,你可以清晰地了解 Kruskal 算法的实际编程过程和细节。该算法在解决最小生成树问题时高效且实用,尤其适用于稀疏图。
7. 如何判断环?
7.1 什么是环(Cycle)?
在图论中,环是指从一个顶点出发,经过一系列边,又回到原来顶点的路径,且路径中除了起点和终点外,其他顶点不重复。
举个简单的例子:
- 顶点 A 连接到 B,B 连接到 C,C 又连接回 A。
- 路径:
A -> B -> C -> A
,这就是一个环。
在构建最小生成树时,我们要避免形成环,因为生成树是一个无环连通子图。
7.2 为什么要检测环?
在 Kruskal 算法中,我们逐步添加权重最小的边。如果不检测环,可能会添加一条边,使得生成树中形成环,违反了生成树的定义。
因此,在每次尝试添加一条边时,需要检查添加这条边是否会形成环。如果会,就不能添加这条边。
7.3 如何检测是否形成环?
为了高效地检测环,Kruskal 算法使用了一种称为并查集(Union-Find,又称为 Disjoint Set Union, DSU) 的数据结构。
7.4 并查集(Union-Find)详解
7.4.1 并查集的概念
- 集合表示:并查集将图中的顶点划分为若干个不相交的集合(初始时,每个顶点都是一个单独的集合)。
- 目的:快速判断两个顶点是否属于同一个集合。
7.4.2 并查集的两个主要操作
查找(Find):
- 用于查找某个元素所属的集合的代表(通常是集合的根节点)。
- 作用:判断两个元素是否在同一个集合中。
合并(Union):
- 将两个不同的集合合并为一个集合。
- 作用:在添加边时,将连接的两个顶点所在的集合合并,表示它们现在是连通的。
7.4.3 检测环的原理
- 核心思想:如果两个顶点在尝试添加边之前已经属于同一个集合,说明它们之间已经连通,再添加这条边会形成环。
- 步骤:
- 对于一条待添加的边,获取其两个顶点的代表(通过 Find 操作)。
- 如果两个代表相同,说明它们在同一个集合中,添加这条边会形成环,需跳过。
- 如果两个代表不同,说明它们不连通,添加这条边不会形成环,进行 Union 操作将两个集合合并。
7.5 举例说明
7.5.1 假设有以下顶点和边:
- 顶点:A, B, C, D
- 边:
- 边1:A - B
- 边2:B - C
- 边3:C - A
7.5.2 初始状态
- 集合:
- {A}
- {B}
- {C}
- {D}
7.5.3 添加边1:A - B
- 查找:
- Find(A) = A
- Find(B) = B
- 判断:A 和 B 不在同一个集合。
- 行动:添加边1,合并集合 {A} 和 {B} 为 {A, B}。
7.5.4 添加边2:B - C
- 查找:
- Find(B) = A(因为 B 的父节点是 A)
- Find(C) = C
- 判断:A和C不在同一个集合。
- 行动:添加边2,合并集合 {A, B} 和 {C} 为 {A, B, C}。
7.5.5 尝试添加边3:C - A
- 查找:
- Find(C) = A
- Find(A) = A
- 判断:A和A相同,说明C和A在同一个集合。
- 结论:添加边3会形成环,跳过此边。
7.6 并查集的实现细节
7.6.1 数据结构
- 父节点数组(或字典):记录每个节点的父节点。
- 初始化:每个节点的父节点初始化为自身。
7.6.2 Find操作
- 递归或迭代地寻找节点的父节点,直到找到根节点(即父节点是自身的节点)。
- 路径压缩优化:
- 在查找的过程中,将经过的节点直接连接到根节点,以加速后续的查找。
示例代码(Find操作):
def find(vertex):
if parent[vertex] != vertex:
parent[vertex] = find(parent[vertex]) # 路径压缩
return parent[vertex]
7.6.3 Union操作
- 合并两个集合,将一个集合的根节点指向另一个集合的根节点。
示例代码(Union操作):
def union(u, v):
root_u = find(u)
root_v = find(v)
if root_u == root_v:
return False # 已在同一集合,形成环
parent[root_v] = root_u # 合并集合
return True
7.7 综合示例
7.7.1 顶点和边
- 顶点:A, B, C, D, E
- 边:
- A - B
- B - C
- C - D
- D - E
- E - A
7.7.2 步骤
初始化:
- 父节点:
- A: A
- B: B
- C: C
- D: D
- E: E
- 父节点:
添加边 A - B
- Find:
- Find(A) = A
- Find(B) = B
- Union:
- 合并A和B,父节点更新为:
- B的父节点为A
- 合并A和B,父节点更新为:
- Find:
添加边 B - C
- Find:
- Find(B) = A
- Find(C) = C
- Union:
- 合并A和C,父节点更新为:
- C的父节点为A
- 合并A和C,父节点更新为:
- Find:
添加边 C - D
- Find:
- Find(C) = A
- Find(D) = D
- Union:
- 合并A和D,父节点更新为:
- D的父节点为A
- 合并A和D,父节点更新为:
- Find:
添加边 D - E
- Find:
- Find(D) = A
- Find(E) = E
- Union:
- 合并A和E,父节点更新为:
- E的父节点为A
- 合并A和E,父节点更新为:
- Find:
尝试添加边 E - A
- Find:
- Find(E) = A
- Find(A) = A
- 判断:
- 两个顶点的根节点相同,说明添加此边会形成环。
- 行动:
- 跳过此边,不添加。
- Find:
7.8 总结
- 环的检测:通过并查集的 Find 操作,判断两个顶点是否在同一个集合。
- 避免形成环:如果两个顶点已连通(在同一集合),则不添加该边。
- 并查集的优势:能够高效地进行合并和查找操作,时间复杂度接近于线性。
7.9 直观理解
- 想象一下:每个集合是一棵树,树的根节点就是集合的代表。
- 查找:从一个节点沿着父节点一路向上,直到根节点。
- 合并:将一个树的根节点连接到另一个树的根节点上。
7.10 实际应用中的提示
- 初始化时,不要忘记将每个节点的父节点设为自身。
- 路径压缩在查找时更新父节点,可以显著提升效率。
- 在代码实现中,确保 Union 操作返回布尔值,以便在 Kruskal 算法中判断是否添加边。
8. Kruskal 和 Prim 区别
Kruskal 算法和 Prim 算法都是解决最小生成树(MST)问题的贪心算法,但它们在实现上有一些关键的区别。这些区别主要体现在选择边的方式、适用的图类型以及底层的数据结构上。
1. 主要区别
区别 | Kruskal算法 | Prim算法 |
---|---|---|
算法类型 | 基于边的选择 | 基于顶点的扩展 |
执行方式 | 按权重对所有边排序,然后依次选取边来构建MST | 从一个起点开始,逐步扩展MST |
适用图类型 | 更适合稀疏图(边较少的图) | 更适合稠密图(边较多的图) |
数据结构 | 并查集(Union-Find) | 最小堆(优先队列) |
2. 详细解释
选择边的方式
Kruskal算法:选择权重最小的边,逐步将这些边添加到最小生成树中,前提是不形成环。Kruskal是基于边的选择,所以它从全局的角度出发,先对所有边排序,再从权重最小的边开始。
Prim算法:从一个起始顶点出发,不断选择与已选顶点连接的权重最小的边扩展MST。因此,Prim是基于顶点的扩展,每次只考虑与当前生成树连接的边。它逐步扩展MST,直到所有顶点都被包括。
执行方式
Kruskal算法:算法先对边按权重排序,然后从权重最小的边开始,逐条检查并加入MST,直到所有顶点连接在一起。对于每条边,都用并查集检查是否会形成环。
Prim算法:Prim算法从一个顶点开始,将与当前生成树相连的最小权重边加入生成树。通过最小堆存储边的权重并逐步扩展,直到生成树覆盖所有顶点。
适用图类型
Kruskal算法:因为Kruskal算法是基于边的选择和排序,对边较少的稀疏图效率更高。边的数量较少,排序和边选择过程会更快。
Prim算法:Prim算法适合边较多的稠密图,因为它从一个顶点逐步扩展,只需要维护与当前生成树相连的边集合。特别是用邻接矩阵或优先队列实现时,效率较高。
数据结构
Kruskal算法:通常使用并查集来管理生成树的连接状态,以便快速合并集合和检测环。
Prim算法:用最小堆或优先队列来维护与当前生成树相连的边,以便快速找到权重最小的边进行扩展。
3. 适用场景举例
Kruskal算法适合场景:适合边较少、图不连通的情况。例如,将一些点连接成网络,而这些点可能分布在较大的区域且连接稀疏。
Prim算法适合场景:适合边较多的连通图。例如,电网、城市道路等密集连接的网络。
4. 总结
- Kruskal 是通过从所有边中选择权重最小的边来逐步构建MST,适合稀疏图。
- Prim 是通过从起始顶点逐步扩展最小生成树,适合稠密图。
公众号:AI悦创【二维码】

AI悦创·编程一对一
AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh
C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh
方法一:QQ
方法二:微信:Jiabcdefh
