ग्राफ का आसन्न सूची और मैट्रिक्स प्रतिनिधित्व
भले ही वे अलग-अलग दिखते हों, लेकिन सभी ग्राफ़ के प्रकार इसी तरह से दर्शाया जा सकता है। आम तौर पर ग्राफ प्रतिनिधित्व के दो प्रकार होते हैं:
- सहखंडज मैट्रिक्स
- आसन्न सूची
आसन्न सूची
एडजेंसी लिस्ट में लिंक्ड लिस्ट शामिल होती हैं। प्रत्येक वर्टेक्स को एक ऐरे इंडेक्स माना जाता है, और प्रत्येक तत्व एक लिंक्ड लिस्ट का प्रतिनिधित्व करता है। इन लिंक्ड लिस्ट में वे वर्टेक्स होते हैं जिनके किनारे इंडेक्स वर्टेक्स के साथ होते हैं।
यहाँ आसन्न सूची का एक उदाहरण दिया गया है:
मान लीजिए कि एक ग्राफ में शीर्षों की संख्या V तथा किनारों की संख्या E है।
सामान्यतः, स्थान जटिलता होगी O(V + E)
.
सबसे खराब स्थिति में अंतरिक्ष जटिलता होगी O(V2)
यदि दिया गया ग्राफ पूर्ण ग्राफ है
सहखंडज मैट्रिक्स
आसन्न मैट्रिक्स 2D सरणी से बना होता है। ग्राफ में शीर्षों की संख्या V है, मैट्रिक्स का आकार होगा VxV
.
कहते हैं, matrix[i][j] = 5
इसका मतलब है कि नोड i और j के बीच एक किनारा है जहां वजन 5 है।
आइये निम्नलिखित ग्राफ और इसके आसन्न मैट्रिक्स को देखें:
हमने बनाया 2डी सरणी इन चरणों का उपयोग करें:
चरण 1) शीर्ष A का B के साथ सीधा किनारा है, तथा भार 5 है। अतः पंक्ति A और स्तंभ B में कक्ष 5 से भरे जाएंगे। पंक्ति A में शेष कक्ष शून्य से भरे जाएंगे।
चरण 2) शीर्ष B का C के साथ सीधा किनारा है, तथा भार 4 है। अतः पंक्ति B और स्तंभ C में कक्ष 4 से भरे जाएंगे। पंक्ति B में शेष कक्ष शून्य से भरे जाएंगे, क्योंकि B का किसी अन्य नोड से कोई बाहरी किनारा नहीं है।
चरण 3) शीर्ष C का किसी अन्य शीर्ष के साथ कोई सीधा किनारा नहीं है। इसलिए, पंक्ति C शून्य से भरी जाएगी।
चरण 4) शीर्ष D में A और C के साथ एक निर्देशित किनारा है।
- यहां, पंक्ति D और स्तंभ A में कक्षों का मान 7 होगा। पंक्ति D और स्तंभ C में कक्षों का मान 2 होगा।
- पंक्ति D की शेष कोशिकाएँ शून्य से भरी जाएंगी।
चरण 5) शीर्ष E में B और D के साथ एक निर्देशित किनारा है। पंक्ति E और स्तंभ B में सेल का मान 6 होगा। पंक्ति E और स्तंभ D में सेल का मान 3 होगा। पंक्ति D में शेष सेल शून्य से भरे जाएंगे।
यहां कुछ ध्यान देने योग्य बातें हैं:
- जब आसन्न मैट्रिक्स का प्राथमिक विकर्ण 0 होता है, तो ग्राफ में कोई स्व-लूप नहीं होता है।
- यदि सूचकांक (a,b) और (b,a) का मान समान नहीं है, तो ग्राफ एक निर्देशित ग्राफ है। अन्यथा, ग्राफ एक निर्देशित ग्राफ है।
- यदि कक्षों का मान 1 से अधिक है तो ग्राफ भारित ग्राफ होगा।
एडजेंसी मैट्रिक्स में कुछ समस्या है क्योंकि इसके लिए वर्गाकार रिक्त स्थान की आवश्यकता होती है। यहाँ, हम उन किनारों को संग्रहीत कर रहे हैं जो जुड़े हुए नहीं हैं। ये किनारे मेमोरी में स्थान आवंटित करते हैं।
उदाहरण के लिए, यदि हमारे पास 100 नोड्स वाला एक ग्राफ है, तो इसे संग्रहीत करने के लिए 10 हजार कोशिकाओं की आवश्यकता होगी। रैमग्राफ़ में कम किनारों के साथ, इतनी बड़ी मेमोरी आवंटित करना बेकार हो सकता है। इसलिए, एडजेंसी मैट्रिक्स का उपयोग करके स्पेस जटिलता होगी O(N2)
, जहाँ N का अर्थ है ग्राफ में नोड्स की संख्या।