एक किमान स्पॅनिंग ट्री (MST) एक भारित, जोडलेल्या आलेखाच्या सर्व शिरोबिंदूंना किमान एकूण किनार वजन सह आणि चक्र न करता जोडते. Kruskal आणि Prim हे दोन शास्त्रीय लोभी अल्गोरिदम आहेत.
Kruskal (किनारे क्रमबद्ध करा, union-find)
सर्व किनारे वजनानुसार क्रमबद्ध करा; सर्वात स्वस्त किनार जोडा जो चक्र तयार करत नाही.
python
():
parent = ((n))
():
parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
x
mst, total = [],
w, u, v (edges):
ru, rv = find(u), find(v)
ru != rv:
parent[ru] = rv
mst.append((u, v, w)); total += w
mst, total