एक किमान स्पॅनिंग ट्री (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 देखील दर्शवते, एक रचना ज्यात व्यापक अल्गोरिदमिक पोचा आहे.
सविस्तर उत्तरांसह IT मुलाखत प्रश्नांचे ग्रंथालय — Junior पासून Senior पर्यंत.
देणगी द्या