Hello दोस्तों! आज मैं आपको इस पोस्ट में Minimal Spanning Tree in Data Structure in Hindi के बारें में बताऊंगा, और इसके example को भी पढेंगे, तो चलिए शुरू करते हैं:-
What is Minimal Spanning Tree in Hindi
Spanning tree वह tree है जो की एक graph द्वारा बनाया जाता है और
एक minimal spanning tree वह spanning tree जिसकी edges की कीमत सबसे कम है
जिस graph (G) से spanning tree का निर्माण किया जा रहा है । उसका connected होना आवश्यक है
यदि graph connected नहीं है तो उससे spanning tree का निर्माण नहीं किया जा सकता है
क्योंकि unconnected graph एक tree कहलाता है ।
यदि कोई tree(T) जो की किसी connected graph का spanning tree है तो-
- Graph (G) की प्रत्येक vertex tree (T) की edge को belong करेगी , और
- Tree (T) मे graph(G) की edge ही tree बनाऐ।
हम किसी graphको minimal spanning tree मे निम्नलिखित दो methods से परिवर्तित कर सकते है
(1) Krushkal’s Method
(2) Prim’s Method
Krushkal’s Method
J. krushkal का सन 1957 मे Propounded(प्रतिपादित) यह method cost spanning tree बनाने का बहुत ही जाना माना तरीका है । यह method graph की edges की एक list पर कार्य करता है ।यहां पर input एक connected weight graph (G) है , जिसमे n vertices है ।
Step1- graph की edges को बढ़ाने क्रम मे व्यवस्थित कर लें ।
Step2- graph (G) की vertices से शुरू होकर बारी – बारी स process करें और प्रत्येक edge को जोड़ें जो एक cycle नहीं बनती है । अथवा जब तक n-1 edges नहीं जुड़ जाती है ।
Step3- exit
यह तरीका तब तक तो लाभदायक है जब तक की ग्राफ छोटा है
क्योंकि इस प्रकार से tree बनाने मे शुरू मे node unconnected रहती है
इसे अब उदाहरण की सहायता से समझते है ।
Step1- graph की edges को बढ़ते क्रम मे व्यवस्थित कर ले।
अब पहली edges से शुरू करते हुये tree को तब तक बनाएँ जब तक की n-1 अर्थात (9-1=8) edges नहीं हो जाती तथा उन्ही edges को जोड़ेंगे जो की cycle नहीं बनती है ।
- हम tree का निर्माण किसी भी 1 weight वाली edge से प्रारम्भ कर सकते है यहां पर हमने AF edge से यह निर्माण प्रारम्भ किया है ।
- यहां पर tree मे एक अन्य 1 weight वाली edge BE को जोड़ लिया है ।
- यहां पर tree मे एक अन्य 1 weight वाली edge ED को जोड़ लिया है ।
- यहां पर tree मे एक अन्य 1 weight वाली edge D1 को जोड़ लिया है।
- यहां पर tree मे एक अन्य 1 weight वाली edge IG को जोड़ लिया है ।
- यहां पर tree मे एक 2 weight वाली edge AB को जोड़ लिया है
क्योकि 1 weight वाली सभी node visit हो चुकी है ।
- यहां पर tree मे एक अन्य 2 weight वाली edge BC को जोड़ लिया है ।
- यहां चूंकि CD एक cycle बना रही है । इसलिये हम इसे नहीं जोड़ेंगे ।
- यहां पर tree मे एक अन्य 2 weight वाली edge GH को जोड़ लिया है ।
जैसे की हम देख सकते है की n-1 (8) edges जुड़ चुकी है । इस tree की कीमत (cost)=1+2+2+1+1+1+1+2+=11 है ।
Prim’s method
Prim का method भी connected graph को spanning tree मे परिवर्तन करने के लिए प्रयोग होता है ।
step1- इसमे एक table साथ – ही –साथ प्रयोग की जाती है,
जिसमे प्रत्येक vertex की adjacent vertices उनके weight के साथ लिखी जाती है ।
Step2- step3 को तब तक दोहराए जब तक की n-1 edges न जुड़ जाए ।
Step3- सबसे कम weight वाली edge को tree मे जोड़े परंतु यह ध्यान रखा जाना चाहिए की कोई भी edge cycle न बनाए ।
Step4- step2 का loop समाप्त हुआ ।
Step5- Exit.
निवेदन:- अगर आपके लिए यह आर्टिकल useful रहा हो तो इसे अपने दोस्तों और classmates के साथ अवश्य share कीजिये, और या अन्य विषयों से related कोई question हो तो नीचे कमेंट के द्वारा बताइए. thanks.