कोडिंग साक्षात्कार की तैयारी · पाठ

Kruskal का Minimum Spanning Tree

cycles बनाए बिना सबसे सस्ती edges जोड़ें

पाठ 3, कुल 4 में से13 चरण

Kruskal का Minimum Spanning Tree, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

MST क्या है

न्यूनतम प्रसारी वृक्ष हर शीर्ष को कुल किनारा-भार को न्यूनतम रखते हुए जोड़ता है और इसमें कोई चक्र नहीं होता। इसे सबसे कम लागत में किसी नगर में तार बिछाने जैसा समझिए। 🌲

Kruskal का मूल विचार

Kruskal का एल्गोरिदम पूरी तरह लालची है: वह सबसे कम भार वाले ऐसे किनारे जोड़ता रहता है जो चक्र न बनाए, जब तक पूरा ग्राफ जुड़ न जाए।

पहला चरण: किनारों को क्रमबद्ध करें

सबसे पहले हर किनारे को उसके भार के अनुसार, छोटे से बड़े क्रम में sort करें। सस्ते किनारों को लालच से प्राथमिकता देने के कारण ही अंतिम कुल भार न्यूनतम होता है।

edges.sort()  # (weight, u, v)

DSU बिल्कुल उपयुक्त क्यों है

कोई किनारा तभी चक्र बनाता है जब उसके दोनों सिरे पहले से जुड़े हों। DSU इस जुड़े होने की जाँच लगभग स्थिर समय में करता है। 🤝

क्रमबद्ध किनारों को देखें

किनारों को सबसे सस्ते से सबसे महँगे क्रम में देखें। हर किनारे के लिए जाँचें कि उसके दोनों सिरे DSU में पहले से एक ही मूल साझा करते हैं या नहीं।

for w, u, v in edges:
    ru, rv = find(u), find(v)

स्वीकार करें या अस्वीकार करें

यदि मूल अलग-अलग हैं, तो किनारा दो अलग हिस्सों को जोड़ता है, इसलिए उसे स्वीकार करके दोनों को संयोजित करें। यदि मूल समान हैं, तो चक्र से बचने के लिए उसे छोड़ दें।

if ru != rv:
    union(u, v)
    total += w

कब रुकना है, जानें

n शीर्षों वाले प्रसारी वृक्ष में ठीक n में से 1 घटाने पर जितने किनारे होते हैं। उतने किनारे स्वीकार करते ही आप जल्दी रुक सकते हैं।

असंबद्धता का पता लगाना

यदि सभी किनारों को देखने के बाद n में से 1 घटाने पर प्राप्त संख्या से कम किनारे स्वीकार हुए हों, तो ग्राफ असंबद्ध है और कोई प्रसारी वृक्ष मौजूद नहीं है।

समय की लागत

क्रमबद्ध करने में सबसे अधिक समय लगता है, इसलिए Kruskal का समय O(E log E) है। DSU के संचालनों की लागत इतनी कम है कि वे कुल समय में लगभग कुछ जोड़ते ही नहीं।

लालची रणनीति सही क्यों है

कट गुणधर्म यह सुनिश्चित करता है कि किसी भी विभाजन को पार करने वाला सबसे हल्का किनारा जोड़ने के लिए सुरक्षित है। इसी कारण सबसे सस्ता किनारा पहले चुनना कभी गलत नहीं होता।

Kruskal का उपयोग कब करें

Kruskal विरल ग्राफों में बहुत अच्छा काम करता है, जब ग्राफ किनारा-सूची के रूप में दिया गया हो—यह वही प्रारूप है जो अधिकांश प्रतियोगी प्रश्न सीधे देते हैं। ⚡

त्वरित जाँच

निर्धारित करें कि Kruskal को किसी किनारे को अस्वीकार करने के लिए क्या बताता है।

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावृत्ति

आपने Kruskal का MST बनाया: किनारों को क्रमबद्ध किया, DSU के माध्यम से दो घटकों को जोड़ने वाला सबसे सस्ता किनारा जोड़ा, और n में से 1 घटाने पर प्राप्त संख्या जितने किनारे होने पर रुक गए। 🎉

शुरुआत निःशुल्क

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 90
पाठ: 360

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Kruskal का Minimum Spanning Tree” पाठ निःशुल्क है?

हाँ—“Kruskal का Minimum Spanning Tree” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Kruskal का Minimum Spanning Tree” में मैं क्या सीखूँगा?

cycles बनाए बिना सबसे सस्ती edges जोड़ें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।

“Kruskal का Minimum Spanning Tree” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ