एक स्पैनिंग ट्री एक अनडायरेक्टेड ग्राफ का एक सबसेट है जिसमें सभी वर्टेक्स न्यूनतम संख्या में एज द्वारा जुड़े होते हैं।
यदि ग्राफ में सभी वर्टेक्स जुड़े हुए हैं, तो कम से कम एक स्पैनिंग ट्री मौजूद होती है। एक ग्राफ में एक से अधिक स्पैनिंग ट्री मौजूद हो सकती हैं।
न्यूनतम स्पैनिंग ट्री
एक न्यूनतम स्पैनिंग ट्री (MST) एक कनेक्टेड वेटेड अनडायरेक्टेड ग्राफ के एज का एक सबसेट है जो सभी वर्टेक्स को न्यूनतम संभव कुल एज वेट के साथ जोड़ता है। MST प्राप्त करने के लिए, प्रिम का एल्गोरिदम या क्रुस्कल का एल्गोरिदम उपयोग किया जा सकता है। इसलिए, हम इस अध्याय में प्रिम के एल्गोरिदम पर चर्चा करेंगे।
जैसा कि हमने चर्चा की, एक ग्राफ में एक से अधिक स्पैनिंग ट्री हो सकती हैं। यदि n संख्या में वर्टेक्स हैं, तो स्पैनिंग ट्री में n - 1 संख्या में एज होने चाहिए। इस संदर्भ में, यदि ग्राफ के प्रत्येक एज से एक वेट जुड़ा हुआ है और एक से अधिक स्पैनिंग ट्री मौजूद हैं, तो हमें ग्राफ की न्यूनतम स्पैनिंग ट्री खोजने की आवश्यकता है।
इसके अलावा, यदि कोई डुप्लिकेट वेटेड एज मौजूद हैं, तो ग्राफ में एक से अधिक न्यूनतम स्पैनिंग ट्री हो सकती हैं।
उपरोक्त ग्राफ में, हमने एक स्पैनिंग ट्री दिखाई है हालांकि यह न्यूनतम स्पैनिंग ट्री नहीं है। इस स्पैनिंग ट्री की लागत (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38 है।
