ஒரு குறைந்தபட்சம் பரவியிருக்கும் மரம் (MST) ஒரு எடையுள்ள, இணைக்கப்பட்ட வரைபடத்தின் அனைத்து உச்சுக்களையும் குறைந்தபட்சம் மொத்த விளிம்பு எடையுடன் இணைக்கிறது மற்றும் சுழல்கள் இல்லை. Kruskal மற்றும் Prim இரண்டு கிளாசிக்கு அলோப முறையான வழிமுறைகள் ஆகும்.
அனைத்து விளிம்புகளையும் எடை மூலம் வரிசைப்படுத்தவும்; சுழல்களை உருவாக்காத மிகவும் மலிவான விளிம்பைச் சேர்க்கவும்.
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
யாதொரு உச்சியிலிருந்தும் தொடங்கவும்; தற்போதைய மரத்தை விட்டு வெளியேறும் மிகவும் மலிவான விளிம்பைச் சேர்க்க மீண்டும் செய்யவும்.
| Kruskal | Prim | |
|---|---|---|
| வழிமுறை | விளிம்புகளை வரிசைப்படுத்தவும் + union-find | ஒரு முனையிலிருந்து வளர்க்கவும் + heap |
| நேரம் | O(E log E) | O(E log V) |
| சிறந்தது | அரிய வரைபடங்கள் | அடர்த்தியான வரைபடங்கள் |
MST ஐ நெட்வொர்க் ডিজাইনுக்கு பயன்படுத்தவும் — கேபிள் போடுதல், நீர் குழாய், கிளাஸ்டரிங். இரண்டும் அலோபம் மற்றும் நிரூபணம் செய்யப்பட்ட உச்சம் இங்கே. Kruskal சுழல்களைத் தவிர்க்க union-find தேவை.
MST அனைத்தையும் இணைக்கும் செலவை குறைக்கிறது — அবকட்டமைப்பு மற்றும் நெட்வொர்க் தளவமைப்பில் நேரடியாக பயன்படுகிறது.
இது ஒரு சுத்தமான வழக்கு அலோபம் நிரூபணம் செய்யப்பட்ட உச்சம் ஆகும், அலோப-தேர்வு பகுத்தறிவை வலுப்படுத்துகிறது.
Kruskal union-find ஐயும் காட்டுகிறது, பரந்த வழிமுறை வரம்பு கொண்ட ஒரு கட்டமைப்பு.