ఒక కనిష్ట వ్యాప్తి చెట్టు (MST) బరువుగల, సంబంధిత గ్రాఫ్ యొక్క అన్ని శీర్షాలను కనిష్ట మొత్తం అంచు బరువుతో కనెక్ట్ చేస్తుంది మరియు చక్రాలు లేవు. Kruskal మరియు Prim రెండు క్లాసిక్ అత్యాశ అల్గోరిథమ్లు.
సమస్త అంచులను బరువు ద్వారా క్రమబద్ధీకరించండి; చక్రాన్ని ఏర్పరచని చcheapest అంచుని జోడించండి.
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
ఏదైనా శీర్షం నుండి ప్రారంభించండి; ప్రస్తుత చెట్టును వదిలి వెళ్ళే సcheapest అంచుని పదేపదే జోడించండి.
| Kruskal | Prim | |
|---|---|---|
| విధానం | అంచులను క్రమబద్ధీకరించండి + union-find | నోడ్ నుండి విస్తరించండి + heap |
| సమయం | O(E log E) | O(E log V) |
| కోసం ఉత్తమం | విరళ గ్రాఫ్లు | దట్ట గ్రాఫ్లు |
MST ను నెట్వర్క్ డిజైన్ కోసం ఉపయోగించండి — కేబిల్ వేయడం, నీటి పైపులు, క్లస్టరింగ్. రెండూ అత్యాశ మరియు నిరూపితమైన సర్వోత్తమ ఇక్కడ. Kruskal చక్రాలను సమర్థవంతంగా నివారించడానికి union-find చేయాలి.
MST ప్రతిదీ కనెక్ట్ చేసే ఖర్చును తగ్గిస్తుంది — మౌలిక సదుపాయాలు మరియు నెట్వర్క్ లేఅవుట్కు నేరుగా వర్తిస్తుంది.
ఇది పరిశుద్ధ సందర్భం ఇక్కడ అత్యాశ నిరూపితమైన సర్వోత్తమం, అత్యాశ-ఎంపిక కారణాన్ని బలపరుస్తుంది.
Kruskal union-find ను కూడా ప్రదర్శిస్తుంది, విస్తృత అల్గోరిథమిక్ రీచ్ ఉన్న నిర్మాణం.
జూనియర్ నుండి సీనియర్ వరకు వివరణాత్మక సమాధానాలతో IT ఇంటర్వ్యూ ప్రశ్నల లైబ్రరీ.
విరాళం