📚克鲁斯卡尔(Kruskal)最小生成树算法详解+模板🌲
发布时间：2025-04-08 03:32:34来源：
在图论的世界里，最小生成树(MST) 是一个超级实用的概念！而 Kruskal 算法 就是解决这一问题的经典算法之一。它通过将边从小到大排序，并逐步选取不会形成环的边来构建一棵树，最终得到最小生成树。🎯
首先，我们需要对所有边按照权重进行排序（从小到大）。然后依次检查每条边，如果这条边连接的两个顶点不在同一个集合中，则将其加入最小生成树，并用并查集（Union-Find）合并这两个集合。这样一来，我们就能避免出现环路啦！🎉
以下是伪代码模板👇：
```python
def kruskal(edges, n):
edges.sort(key=lambda x: x[2]) 按权重排序
parent = list(range(n))
def find(u):
while parent[u] != u:
parent[u] = parent[parent[u]]
u = parent[u]
return u
mst_cost = 0
for u, v, w in edges:
pu, pv = find(u), find(v)
if pu != pv:
parent[pv] = pu
mst_cost += w
return mst_cost
```
简单高效，是不是很酷？👏 快去试试吧！💪
免责声明：本答案或内容为用户上传，不代表本网观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。 如遇侵权请及时联系本站删除。
