ग्राफ का आसन्न सूची और मैट्रिक्स प्रतिनिधित्व
सारा चेन
⚡ स्मार्ट सारांश
ग्राफ के एडजसेंसी लिस्ट और मैट्रिक्स निरूपण में वर्टेक्स और एज को मेमोरी में स्टोर किया जाता है, जिससे एल्गोरिदम नेटवर्क को ट्रैवर्स कर सकते हैं। एडजसेंसी लिस्ट प्रत्येक वर्टेक्स के लिए लिंक्ड लिस्ट का उपयोग करती है, जबकि एडजसेंसी मैट्रिक्स एक वर्गाकार द्वि-आयामी ग्रिड का उपयोग करती है।
भले ही वे अलग-अलग दिखते हों, लेकिन सभी ग्राफ़ के प्रकार इसे समान तरीके से दर्शाया जा सकता है। ग्राफ निरूपण के सामान्यतः दो प्रकार होते हैं:
- सहखंडज मैट्रिक्स
- आसन्न सूची
आसन्न सूची
एक एडजसेंसी लिस्ट में लिंक्ड लिस्ट शामिल होती हैं। प्रत्येक वर्टेक्स को एक ऐरे इंडेक्स माना जाता है, और प्रत्येक एलिमेंट एक लिंक्ड लिस्ट को दर्शाता है। इन लिंक्ड लिस्ट में वे वर्टेक्स होते हैं जो इंडेक्स वर्टेक्स के साथ एक एज साझा करते हैं।
यहां एक आसन्नता सूची का उदाहरण दिया गया है:
मान लीजिए कि एक ग्राफ में V शीर्ष और E किनारे हैं। आसन्नता सूची की स्थानिक जटिलता क्या है? O(V + E)जो कि शीर्षों के प्रत्येक संभावित जोड़े के बजाय वास्तविक किनारों की संख्या के साथ बढ़ता है।
सबसे खराब स्थिति में स्थानिक जटिलता बन जाती है O(V²) यदि दिया गया ग्राफ एक पूर्ण ग्राफ है, तो इसका कारण यह है कि प्रत्येक शीर्ष अन्य सभी शीर्षों से जुड़ा होता है।
सहखंडज मैट्रिक्स
एक एडजसेंसी मैट्रिक्स एक 2D एरे से बना होता है। V वर्टेक्स वाले ग्राफ के लिए, मैट्रिक्स का आकार होगा V × V.
कहना 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 होगा। पंक्ति E के शेष सभी सेल शून्य से भरे होंगे।
यहां कुछ ध्यान देने योग्य बातें हैं:
- जब आसन्नता मैट्रिक्स का प्राथमिक विकर्ण 0 होता है, तो ग्राफ में कोई स्व-लूप नहीं होता है।
- यदि बिंदु (a, b) और (b, a) पर स्थित सेल का मान समान न हो, तो ग्राफ एक निर्देशित ग्राफ कहलाता है। अन्यथा, ग्राफ अनिर्देशित होता है।
- यदि किसी भी सेल का मान 1 से अधिक है तो ग्राफ भारित ग्राफ कहलाता है।
एडजसेंसी मैट्रिक्स की मुख्य समस्या यह है कि इसके लिए वर्गाकार स्थान की आवश्यकता होती है। यहां तक कि जो किनारे मौजूद नहीं हैं, वे भी मेमोरी में सेल आवंटित करते हैं।
उदाहरण के लिए, यदि हमारे पास 100 नोड्स वाला एक ग्राफ है, तो उसे स्टोर करने के लिए 10,000 सेल्स की आवश्यकता होगी। रैमग्राफ में किनारों की संख्या कम होने पर, इतनी बड़ी मेमोरी आवंटित करना व्यर्थ हो सकता है। इसलिए आसन्न मैट्रिक्स का उपयोग करके स्थान जटिलता यह है: O(N²)जहां N ग्राफ में नोड्स की संख्या है।
एडजसेंसी लिस्ट बनाम एडजसेंसी मैट्रिक्स
किसी भी प्रतिनिधित्व को चुनने से पहले, वास्तविक ग्राफ वर्कलोड में हावी रहने वाले ऑपरेशनों के आधार पर दोनों मॉडलों की तुलना करना सहायक होता है:
| Operaउत्पादन | सहखंडज मैट्रिक्स | आसन्न सूची |
|---|---|---|
| अंतरिक्ष की जटिलता | ओ(वी²) | ओ(वी + ई) |
| एक शीर्ष जोड़ें | ओ(वी²) | ओ (1) |
| एक नया किनारा जोड़ें | ओ (1) | ओ (1) |
| एक किनारे को हटा दें | ओ (1) | ओ(ई) |
| जांचें कि किनारा (i, j) मौजूद है या नहीं | ओ (1) | O(i की डिग्री) |
| i के पड़ोसियों पर पुनरावृति करें | ओ(वी) | O(i की डिग्री) |
| के लिए सबसे अच्छा | सघन ग्राफ़, बार-बार एज क्वेरी | विरल ग्राफ़, ट्रैवर्सल-भारी कार्य |
संक्षेप में, स्थिर समय में एज लुकअप के मामले में एडजसेंसी मैट्रिक्स बेहतर है, जबकि मेमोरी और पड़ोसी पुनरावृति के मामले में एडजसेंसी लिस्ट बेहतर है, यही कारण है कि बीएफएस, डीएफएस और डाइक्स्ट्रा जैसे एल्गोरिदम आमतौर पर एडजसेंसी लिस्ट के साथ उपयोग किए जाते हैं।
ग्राफ निरूपण के लाभ और हानियाँ
प्रत्येक प्रस्तुतिकरण की अपनी-अपनी खूबियाँ और कमियाँ होती हैं। दोनों मॉडलों की खूबियों और कमियों को जानने से आपको उस समस्या के लिए सही मॉडल चुनने में मदद मिलती है जिसका आप समाधान कर रहे हैं।
एडजसेंसी मैट्रिक्स के लाभ:
- किसी भी जोड़ी शीर्षों के बीच स्थिर समय O(1) किनारे-अस्तित्व क्वेरी।
- निश्चित अनुक्रमणिका के कारण फ्लोयड-वार्शाल और ट्रांजिटिव क्लोजर जैसे मैट्रिक्स-आधारित एल्गोरिदम को लागू करना आसान हो जाता है।
- भारित किनारे एक ही मैट्रिक्स सेल में स्वाभाविक रूप से फिट हो जाते हैं।
एडजसेंसी मैट्रिक्स के नुकसान:
- ग्राफ के विरल होने पर O(V²) मेमोरी की बर्बादी होती है।
- एक नया वर्टेक्स जोड़ने के लिए पूरी मैट्रिक्स का आकार बदलना आवश्यक है।
- किसी एक शीर्ष के पड़ोसियों पर पुनरावृति करने में O(V) समय लगता है, भले ही उस शीर्ष में केवल कुछ ही किनारे हों।
एडजसेंसी लिस्ट के फायदे:
- यह केवल O(V + E) मेमोरी का उपयोग करता है, जो विरल ग्राफ़ में वास्तविक किनारों की संख्या के करीब है।
- एक नया शीर्ष या किनारा जोड़ना O(1) है।
- बीएफएस और डीएफएस जैसे ट्रैवर्सल एल्गोरिदम पड़ोसियों को ओ (डिग्री) में दोहराते हैं, जिससे कुल मिलाकर ओ (वी + ई) चलने का समय मिलता है।
एडजसेंसी लिस्ट के नुकसान:
- किसी विशिष्ट किनारे के अस्तित्व की जाँच करने में O(1) के बजाय O(डिग्री) समय लगता है।
- लिंक्ड लिस्ट मेमोरी में बिखरी होने के कारण कैश लोकैलिटी कमजोर होती है।
- भारित किनारों के लिए एक साथी फ़ील्ड या युग्मों की सूची की आवश्यकता होती है, जिससे डेटा संरचना थोड़ी जटिल हो जाती है।
एडजसेंसी लिस्ट बनाम एडजसेंसी मैट्रिक्स का उपयोग कब करें
ग्राफ़ के घनत्व और आपके द्वारा सबसे अधिक बार किए जाने वाले ऑपरेशनों के आधार पर प्रतिनिधित्व का चुनाव किया जाता है। सही संरचना चुनने के लिए इस त्वरित मार्गदर्शिका का उपयोग करें:
- आसन्नता मैट्रिक्स को प्राथमिकता दें जब ग्राफ सघन होता है (E, V² के करीब होता है), जब किनारे शायद ही कभी बदलते हैं, और जब आपका एल्गोरिदम कई बार पूछता है कि "क्या i और j के बीच कोई किनारा है?"
- आसन्नता सूची को प्राथमिकता दें जब ग्राफ़ विरल होता है (E, V² से बहुत छोटा होता है), जब निष्पादन के दौरान शीर्ष या किनारों का समूह बढ़ता है, और जब आप BFS, DFS, या डाइक्स्ट्रा का सबसे छोटा पथ एल्गोरिदम.
- मिश्रित मॉडल को प्राथमिकता दें (आसन्नता सूची प्लस किनारों का एक हैश सेट) जब आपको अतिरिक्त मेमोरी की कीमत पर तेज़ पड़ोसी पुनरावृति और O(1) एज क्वेरी दोनों की आवश्यकता होती है।
NetworkX और igraph जैसी आधुनिक ग्राफ लाइब्रेरी डिफ़ॉल्ट रूप से एडजसेंसी सूचियों का उपयोग करती हैं क्योंकि अधिकांश वास्तविक दुनिया के ग्राफ - सोशल नेटवर्क, रोड मैप, वेब पेज, पैकेज निर्भरता - विरल और ट्रैवर्सल-भारी होते हैं।
