🎉 Kruskal算法简易教程 | 附最全注释代码实现 📊

Kruskal算法是解决最小生成树的经典方法之一，尤其适合图论初学者掌握！它通过贪心策略，从边的角度出发，逐步构建最优解。🔍

首先，我们需要对所有边按权重从小到大排序。然后依次尝试将边加入结果集中，但需确保不会形成环（可通过并查集检测）。如果满足条件，则这条边被保留；否则跳过。💡

以下是Python代码实现👇

```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

result = []

for u, v, w in edges:

root_u, root_v = find(u), find(v)

if root_u != root_v: 不构成环

result.append((u, v, w))

parent[root_u] = root_v

return result

```

测试实例：

输入：

`edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]`

输出：

`[(0, 3, 5), (2, 3, 4), (0, 1, 10)]`

通过Kruskal算法，我们轻松找到全局最优解！🌟

算法 图论 最小生成树