图论中的最小生成树算法:Kruskal算法详解与实现
创作时间:
作者:
@小白创作中心
图论中的最小生成树算法:Kruskal算法详解与实现
引用
CSDN
1.
https://blog.csdn.net/m0_49844155/article/details/146488052
最小生成树算法是图论中的一个重要概念,广泛应用于网络设计、电路布线等领域。本文将详细介绍Kruskal算法,一种基于边的最小生成树算法,并通过具体示例和代码实现帮助读者深入理解。
Kruskal算法简介
Kruskal算法用于求解图的最小生成树问题。与Prim算法不同,Kruskal算法是通过维护边的集合来实现的。其基本思路如下:
- 将图中的所有边按照权值从小到大排序
- 依次遍历排序后的边
- 如果边的两个端点不在同一个集合中,则将这条边加入最小生成树,并将两个端点所在的集合合并
- 重复步骤3,直到最小生成树包含所有节点
算法步骤详解
以一个具体的图为例,说明Kruskal算法的工作过程:
- 首先将图中的边按照权值从小到大排序:[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]
- 依次遍历排序后的边:
- 选边(1,2),节点1 和 节点2 不在同一个集合,所以生成树可以添加边(1,2),并将 节点1,节点2 放在同一个集合。
- 选边(4,5),节点4 和 节点 5 不在同一个集合,生成树可以添加边(4,5) ,并将节点4,节点5 放到同一个集合。
- 选边(1,3),节点1 和 节点3 不在同一个集合,生成树添加边(1,3),并将节点1,节点3 放到同一个集合。
- 选边(2,6),节点2 和 节点6 不在同一个集合,生成树添加边(2,6),并将节点2,节点6 放到同一个集合。
- 选边(3,4),节点3 和 节点4 不在同一个集合,生成树添加边(3,4),并将节点3,节点4 放到同一个集合。
- 选边(6,7),节点6 和 节点7 不在同一个集合,生成树添加边(6,7),并将 节点6,节点7 放到同一个集合。
- 选边(5,7),节点5 和 节点7 在同一个集合,不做计算。
- 选边(1,5),两个节点在同一个集合,不做计算。
- 后面遍历 边(3,2),(2,4),(5,6) 同理,都因两个节点已经在同一集合,不做计算。
最终生成的最小生成树如下:
并查集的应用
在Kruskal算法中,需要判断两个节点是否在同一个集合,以及将两个节点加入同一个集合。这正是并查集的主要功能:
- 将两个元素添加到一个集合中
- 判断两个元素在不在同一个集合
因此,在实现Kruskal算法时,通常会使用并查集来管理节点的集合关系。
代码实现
以下是Kruskal算法的C++实现:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// l,r为 边两边的节点,val为边的数值
struct Edge {
int l, r, val;
};
// 节点数量
int n = 10001;
// 并查集标记节点关系的数组
vector<int> father(n, -1); // 节点编号是从1开始的,n要大一些
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
// 并查集的查找操作
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}
// 并查集的加入集合
void join(int u, int v) {
u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (u == v) return ; // 如果发现根相同,则说明在一个集合,不用两个节点相连直接返回
father[v] = u;
}
int main() {
int v, e;
int v1, v2, val;
vector<Edge> edges;
int result_val = 0;
cin >> v >> e;
while (e--) {
cin >> v1 >> v2 >> val;
edges.push_back({v1, v2, val});
}
// 执行Kruskal算法
// 按边的权值对边进行从小到大排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.val < b.val;
});
// 并查集初始化
init();
// 从头开始遍历边
for (Edge edge : edges) {
// 并查集,搜出两个节点的祖先
int x = find(edge.l);
int y = find(edge.r);
// 如果祖先不同,则不在同一个集合
if (x != y) {
result_val += edge.val; // 这条边可以作为生成树的边
join(x, y); // 两个节点加入到同一个集合
}
}
cout << result_val << endl;
return 0;
}
以下是Kruskal算法的Python实现:
import sys
# 边的数据结构
class Edge():
def __init__(self, s, t, val):
self.s = s # 边起点
self.t = t # 边终点
self.val = val # 边权值
# 并查集
class unionFind():
def __init__(self, n):
self.n = n # 结点总个数
self.father = list(range(v + 1)) # 子->父结点映射,这个里的结点是节点编号如edge.s,不是Edge的实例!
def find(self, u):
if u != self.father[u]:
self.father[u] = self.find(self.father[u])
return self.father[u]
def isSame(self, u, v):
return self.find(u) == self.find(v)
def join(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
self.father[root_v] = root_u
if __name__ == '__main__':
lines = sys.stdin.readlines()
v, e = map(int, lines[0].strip().split()) # 定点数v,边数e
# 创建边集合
edges = []
for i in range(1, len(lines)):
# 边起点,边终点,边权值
s, t, val = map(int, lines[i].strip().split())
edges.append(Edge(s, t, val))
# 按照边权值升序排序edges
edges.sort(key=lambda edge: edge.val)
# 创建并查集,从最小边权值开始遍历边:每条边
# 如果两端点非同根(不都在并查集中),则说明当前边加入之后不会成环,直接加入生成树即可;
# 如果两端点同根,说明当前边加入之后会成环,不能入树
ans = 0 # 记录最小权值(最短距离)路径的权值和(距离和)
uf = unionFind(v) # 创建并查集
for edge in edges:
# 非同根情况才需要操作,同根时直接跳过
if not uf.isSame(edge.s, edge.t):
uf.join(edge.s, edge.t)
ans += edge.val
print(ans)
拓展应用
输出最小生成树的边
如果需要输出最小生成树的边,可以在判断两个节点不在同一个集合时,将这条边保存下来:
vector<Edge> result; // 存储最小生成树的边
// 如果祖先不同,则不在同一个集合
if (x != y) {
result.push_back(edge); // 记录最小生成树的边
result_val += edge.val; // 这条边可以作为生成树的边
join(x, y); // 两个节点加入到同一个集合
}
算法选择策略
Kruskal算法和Prim算法各有优劣:
- Kruskal算法:适用于边较少的稀疏图,时间复杂度为O(nlogn),其中n为边的数量。
- Prim算法:适用于节点较少的稠密图,时间复杂度为O(n^2),其中n为节点数量。
因此,在选择算法时,需要根据图的特性来决定:
- 如果图中节点多但边少,使用Kruskal算法更优。
- 如果图中节点少但边多,使用Prim算法更优。
热门推荐
DAB型微逆变器仿真研究与新型调制策略
市场洞察岗位的职业发展路径是怎样的?
资治通鉴里的职场启发,有技术不一定被重视
中考真要取消?十年纲要真相曝光!职普融通如何改变升学路
如何制定高效的开发计划?掌握这些关键步骤!
为什么说音乐是一种心境?
华为六位密码强制解锁(密码强制解锁的技术挑战与法律争议)
台风来临时,如果住在高楼应注意哪些事项?
团队拍摄素材如何管理
用准确、具体、生动的词汇支撑文章的观点
美国的物价究竟高不高?受哪些因素影响?
如何查看美国物价情况?美国物价的变化趋势如何分析?
当弑神者成为福音:解构《新世纪福音战士》的末世狂想
养猪场猪病与疫情频发的深度解析与应对策略
红楼梦中《芙蓉女儿诔》是谁作的?背后有何深意?
十神的基础入门
空投新手必看:如何避免被标记为"女巫"
毛孔粗大痘印痘坑怎么修复
介入治疗科普:创伤小、恢复快的现代医疗技术
全球快速转型时代下技能和劳动力发展的九大变革趋势
灭火器取消年检(定期维修)的来龙去脉
注塑工艺基础知识培训
你应该知道的头痛常见原因
陕西历史博物馆和考古博物馆哪个好
微信视频号开通指南
如何选择符合人体工学的办公桌椅以提升员工舒适度?
不同地区数据中心空调系统节能技术应用分析
春季,成了口腔溃疡的“春天”?为什么容易溃疡?如何预防和治疗
淘宝退货宝不够支付实际运费该怎么办?运费超过运费险后如何补差价呢?
黑眼圈遮瑕秘技:两位化妆师分享终极解决方案