Minimum Spanning Tree in Hindi | मिनिमम स्पैनिंग ट्री क्या है?

मिनिमम स्पैनिंग ट्री क्या है? (Minimum Spanning Tree in Hindi)

मिनिमम स्पैनिंग ट्री (Minimum Spanning Tree - MST) एक कनेक्टेड, वेटेड ग्राफ का सबसे छोटा उप-ग्राफ (Subgraph) होता है, जिसमें सभी वर्टिस (Vertices) आपस में जुड़े होते हैं और कुल वजन (Weight) न्यूनतम होता है। यह ट्री किसी भी साइकल (Cycle) को शामिल नहीं करता है।

मिनिमम स्पैनिंग ट्री के गुण (Properties of Minimum Spanning Tree)

• यह n वर्टिस और n-1 एजेस (Edges) वाला एक ट्री होता है।
• कोई भी ग्राफ का एक से अधिक MST हो सकता है।
• यह किसी कनेक्टेड ग्राफ का न्यूनतम भार वाला ट्री होता है।
• कोई भी MST कोई साइकल (Cycle) नहीं बनाता।

MST खोजने के एल्गोरिदम (Algorithms for Finding Minimum Spanning Tree)

प्रिम्स एल्गोरिदम (Prim's Algorithm for MST)

प्रिम्स एल्गोरिदम ग्राफ में सेलेक्टेड वर्टिस के साथ न्यूनतम वेट वाला एज जोड़कर कार्य करता है।

1. एक वर्टेक्स से शुरुआत करें और इसे MST में जोड़ें।
2. सभी जुड़े एजेस को देखें और न्यूनतम वेट वाला एज चुनें।
3. चयनित एज को MST में जोड़ें।
4. इस प्रक्रिया को तब तक दोहराएं जब तक सभी वर्टिस MST में शामिल न हो जाएं।

क्रुस्कल एल्गोरिदम (Kruskal's Algorithm for MST)

क्रुस्कल एल्गोरिदम सभी एजेस को वेट के आधार पर सॉर्ट करता है और फिर न्यूनतम वेट वाले एजेस को जोड़कर ट्री बनाता है।

1. सभी एजेस को उनके वेट के अनुसार सॉर्ट करें।
2. सबसे छोटा एज चुनें और इसे MST में जोड़ें (यदि यह कोई साइकल नहीं बनाता)।
3. इस प्रक्रिया को तब तक दोहराएं जब तक n-1 एजेस MST में न हों।

मिनिमम स्पैनिंग ट्री का उदाहरण (Example of Minimum Spanning Tree)

माना कि हमारे पास निम्नलिखित ग्राफ है:

इस ग्राफ के लिए MST निम्नलिखित एजेस का होगा:

• (B - C) : 1
• (A - B) : 2
• (B - D) : 4

मिनिमम स्पैनिंग ट्री की समय जटिलता (Time Complexity of MST)

• Prim's Algorithm: O(E log V) – Priority Queue के साथ।
• Kruskal's Algorithm: O(E log E) – Sorting के कारण।

मिनिमम स्पैनिंग ट्री के अनुप्रयोग (Applications of MST)

• नेटवर्क डिज़ाइन (Network Design) – कंप्यूटर नेटवर्क, टेलीफोन नेटवर्क।
• क्लस्टरिंग एल्गोरिदम (Clustering Algorithm) में उपयोग।
• इमेज सेगमेंटेशन और ग्राफ-आधारित समस्याओं में।

निष्कर्ष

मिनिमम स्पैनिंग ट्री किसी ग्राफ के न्यूनतम भार वाले कनेक्टेड ट्री को खोजने के लिए उपयोग किया जाता है। इसके लिए प्रिम्स और क्रुस्कल एल्गोरिदम सबसे प्रसिद्ध एल्गोरिदम हैं, जिनका उपयोग कंप्यूटर नेटवर्क, ग्राफ थ्योरी और डेटा क्लस्टरिंग में किया जाता है।