ਇੱਕ ਘੱਟੋ-ਘੱਟ ਫੈਲਦਾ ਵਿਸ਼ਾ (MST) ਇੱਕ ਭਾਰਿਤ, ਜੁੜੇ ਹੋਏ ਗ੍ਰਾਫ ਦੇ ਸਾਰੇ ਸਿਖਰਾਂ ਨੂੰ ਘੱਟੋ-ਘੱਟ ਕੁਲ ਕਿਨਾਰੇ ਦਾ ਭਾਰ ਅਤੇ ਕੋਈ ਚੱਕਰ ਨਾ ਹੋਣ ਨਾਲ ਜੋੜਦਾ ਹੈ। ਕ੍ਰਸਕਲ ਅਤੇ ਪ੍ਰਿਮ ਦੋ ਕਲਾਸਿਕ ਲਾਲਸਾ ਹੋਈ ਐਲਗੋਰਿਦਮ ਹਨ।
ਸਾਰੇ ਕਿਨਾਰਿਆਂ ਨੂੰ ਭਾਰ ਦੁਆਰਾ ਛਾਂਟੋ; ਸਭ ਤੋਂ ਸਸਤੀ ਲੀ ਕਿਨਾਰਾ ਜੋੜੋ ਜੋ ਕੋਈ ਚੱਕਰ ਨਹੀਂ ਬਣਾਉਂਦਾ।
def kruskal(n, edges): # edges: (weight, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # cheapest first
ru, rv = find(u), find(v)
if ru != rv: # no cycle -> take it
parent[ru] = rv
mst.append((u, v, w)); total += w
return mst, total
ਕਿਸੇ ਵੀ ਸਿਖਰ ਤੋਂ ਸ਼ੁਰੂ ਕਰੋ; ਬਾਰ-ਬਾਰ ਸਭ ਤੋਂ ਸਸਤੀ ਲਾ ਕਿਨਾਰਾ ਜੋੜੋ ਜੋ ਮੌਜੂਦਾ ਵਿਸ਼ੇ ਤੋਂ ਬਾਹਰ ਜਾਂਦਾ ਹੈ।
| ਕ੍ਰਸਕਲ | ਪ੍ਰਿਮ | |
|---|---|---|
| ਰੁੱਖ | ਕਿਨਾਰਿਆਂ ਨੂੰ ਛਾਂਟੋ + union-find | ਨੋਡ ਤੋਂ ਉਗਾਓ + heap |
| ਸਮਾਂ | O(E log E) | O(E log V) |
| ਸਭ ਨਾਲ ਵਧੀਆ | ਖਿੱਲੀ-ਖਾਲੀ ਗ੍ਰਾਫ | ਘਣੀ ਗ੍ਰਾਫ |
ਨੈਟਵਰਕ ਡਿਜ਼ਾਈਨ ਲਈ MST ਵਰਤੋ — ਕੇਬਲ ਲਾਉਣਾ, ਪਾਣੀ ਦੀਆਂ ਨਾਲੀਆਂ, ਕਲਸਟਰਿੰਗ। ਦੋਨੋਂ ਲਾਲਸਾ ਹੋਏ ਅਤੇ ਸਾਬਤ ਕੀਤੇ ਸਵੋਤਮ ਹਨ। ਕ੍ਰਸਕਲ ਨੂੰ ਚੱਕਰਾਂ ਤੋਂ ਪਰਹੇਜ਼ ਕਰਨ ਲਈ union-find ਦੀ ਲੋੜ ਹੈ।
MST ਸਭ ਕੁਝ ਜੋੜਨ ਦੀ ਲਾਗਤ ਨੂੰ ਘੱਟ ਕਰਦਾ ਹੈ — ਬਿਲਕੁਲ ਢਾਂਚੇ ਅਤੇ ਨੈਟਵਰਕ ਲੇਆਊਟ ਉਲੱਥ ਹੈ।
ਇਹ ਇੱਕ ਸਾਫ਼ ਸਥਿਤੀ ਹੈ ਜਿੱਥੇ ਲਾਲਸਾ ਸਾਬਤ ਮਾਤਰ ਸਵੋਤਮ ਹੈ, ਲਾਲਸਾ-ਚੋਣ ਵਿਚਾਰ ਨੂੰ ਮਜ਼ਬੂਤ ਕਰਦਾ ਹੈ।
ਕ੍ਰਸਕਲ ਵਿ union-find ਵਿ ਪ੍ਰਦਰਸ਼ਨ ਕਰਦਾ ਹੈ, ਇੱਕ ਢਾਂਚਾ ਜਿਸ ਕੋਲ ਵਿਆਪਕ ਐਲਗੋਰਿਦਮਿਕ ਪਹੁੰਚ ਹੈ।