正在打开模型库
正在打开模型库
用最小总代价把所有点连成一体，且没有圈。
先连最便宜又不会成圈的边，直到全部连通。
目标是“连通且最省”而不是“两点最短”时用。
Python 代码
edges = [(1, 0, 1), (2, 0, 2), (2, 1, 2), (3, 1, 3), (4, 2, 3)]
parent = [0, 1, 2, 3]
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = 0
for w, u, v in sorted(edges):
a, b = find(u), find(v)
if a != b:
parent[a] = b
total += w
print(total)