ग्राफ़ संग्रहीत करने के लिए डेटा संरचनाएँ: मौजूदा और दो "लगभग नए" की समीक्षा

नमस्कार.

इस नोट में, मैंने कंप्यूटर विज्ञान में ग्राफ़ को संग्रहीत करने के लिए उपयोग की जाने वाली मुख्य डेटा संरचनाओं को सूचीबद्ध करने का निर्णय लिया, और मैं कुछ और ऐसी संरचनाओं के बारे में भी बात करूंगा जो किसी तरह मेरे लिए "क्रिस्टलीकृत" हुईं।

तो, चलिए शुरू करते हैं। लेकिन शुरुआत से नहीं - मुझे लगता है कि हम सभी पहले से ही जानते हैं कि एक ग्राफ़ क्या है और वे क्या हैं (निर्देशित, अप्रत्यक्ष, भारित, अभारित, कई किनारों और लूप के साथ या बिना)।

तो चलते हैं। "ग्राफ भंडारण" के लिए डेटा संरचनाओं के लिए हमारे पास क्या विकल्प हैं?

1. मैट्रिक्स डेटा संरचनाएँ

1.1 सहखंडज मैट्रिक्स। आसन्न मैट्रिक्स एक मैट्रिक्स है जहां पंक्ति और स्तंभ शीर्षक ग्राफ़ के शीर्षों की संख्या के अनुरूप होते हैं, और इसके प्रत्येक तत्व a(i,j) का मान शीर्षों के बीच किनारों की उपस्थिति या अनुपस्थिति से निर्धारित होता है i और j (यह स्पष्ट है कि एक अप्रत्यक्ष ग्राफ़ के लिए ऐसा मैट्रिक्स सममित होगा, या हम सहमत हो सकते हैं कि हम सभी मानों को केवल मुख्य विकर्ण के ऊपर संग्रहीत करते हैं)। बिना भारित ग्राफ़ के लिए, a(i,j) को i से j तक किनारों की संख्या द्वारा सेट किया जा सकता है (यदि ऐसा कोई किनारा नहीं है, तो a(i,j)= 0), और भारित ग्राफ़ के लिए, वज़न द्वारा भी सेट किया जा सकता है (कुल वजन) उल्लिखित किनारों का।

1.2 घटना मैट्रिक्स. इस मामले में, हमारा ग्राफ़ एक तालिका में भी संग्रहीत होता है जिसमें, एक नियम के रूप में, पंक्ति संख्याएँ इसके शीर्षों की संख्या के अनुरूप होती हैं, और स्तंभ संख्याएँ पूर्व-क्रमांकित किनारों के अनुरूप होती हैं। यदि एक शीर्ष और एक किनारा एक-दूसरे पर आपतित होते हैं, तो संबंधित सेल में एक गैर-शून्य मान लिखा जाता है (अप्रत्यक्ष ग्राफ़ के लिए, यदि शीर्ष और किनारा आपतित होते हैं तो 1 लिखा जाता है, उन्मुख ग्राफ़ के लिए - "1" यदि किनारा शीर्ष से "बाहर निकलता है" और "-1" यदि यह इसमें "शामिल" होता है (यह याद रखना काफी आसान है, क्योंकि "माइनस" चिह्न भी संख्या "-1" में "शामिल" लगता है))। भारित ग्राफ़ के लिए, फिर से, 1 और -1 के बजाय, आप किनारे का कुल वजन निर्दिष्ट कर सकते हैं।

2. गणना डेटा संरचनाएं

2.1 निकटवर्ती सूची. खैर, यहाँ सब कुछ सरल प्रतीत होता है। ग्राफ़ का प्रत्येक शीर्ष, सामान्य तौर पर, किसी भी गणना संरचना (सूची, वेक्टर, सरणी, ...) से जुड़ा हो सकता है, जो दिए गए शीर्ष से सटे सभी शीर्षों की संख्या संग्रहीत करेगा। निर्देशित ग्राफ़ के लिए, हम ऐसी सूची में केवल उन शीर्षों को जोड़ेंगे जिन पर किसी फीचर शीर्ष से "निर्देशित" किनारा है। भारित ग्राफ़ के लिए कार्यान्वयन अधिक जटिल होगा।

2.2 पसलियों की सूची. काफी लोकप्रिय डेटा संरचना. किनारों की सूची, जैसा कि कैप्टन ओब्विअसनेस हमें बताता है, वास्तव में ग्राफ़ के किनारों की एक सूची है, जिनमें से प्रत्येक को प्रारंभिक शीर्ष, अंतिम शीर्ष द्वारा निर्दिष्ट किया जाता है (अप्रत्यक्ष ग्राफ़ के लिए क्रम यहां महत्वपूर्ण नहीं है, हालांकि एकीकरण के लिए आप कर सकते हैं) विभिन्न नियमों का उपयोग करें, उदाहरण के लिए, बढ़ते क्रम में शीर्षों को निर्दिष्ट करना) और वजन (केवल भारित ग्राफ़ के लिए)।

आप ऊपर सूचीबद्ध मैट्रिक्स सूचियों को अधिक विस्तार से (और चित्रों के साथ) देख सकते हैं, उदाहरण के लिए, यहां.

2.3 निकटवर्ती सरणी. सबसे सामान्य संरचना नहीं. इसके मूल में, यह एक गणना संरचना (सरणी, वेक्टर) में आसन्न सूचियों को "पैकिंग" करने का एक रूप है। ऐसे सरणी के पहले n (ग्राफ़ के शीर्षों की संख्या के अनुसार) तत्वों में उसी सरणी के शुरुआती सूचकांक होते हैं, जिससे शुरू होकर दिए गए शीर्ष से सटे सभी शीर्ष एक पंक्ति में लिखे जाते हैं।

यहां मुझे सबसे अधिक समझने योग्य (अपने लिए) स्पष्टीकरण मिला: ejuo.livejournal.com/4518.html

3. आसन्न वेक्टर और सहयोगी आसन्न सरणी

यह पता चला कि इन पंक्तियों के लेखक, एक पेशेवर प्रोग्रामर नहीं हैं, लेकिन जो समय-समय पर ग्राफ़ से निपटते हैं, अक्सर किनारों की सूचियों से निपटते हैं। वास्तव में, यह सुविधाजनक है यदि ग्राफ़ में एकाधिक लूप और किनारे हों। और इसलिए, किनारों की क्लासिक सूचियों के विकास में, मैं उनके "विकास/शाखा/संशोधन/उत्परिवर्तन" पर ध्यान देने का प्रस्ताव करता हूं, अर्थात्: आसन्न वेक्टर और सहयोगी आसन्न सरणी।

3.1 आसन्नता वेक्टर

केस (ए1): अभारित ग्राफ

हम एक अभारित ग्राफ़ के लिए एक आसन्नता वेक्टर को पूर्णांकों की सम संख्या (a[2i], a[2i+1],..., जहां i को c 0 क्रमांकित किया गया है) का एक क्रमबद्ध सेट कहेंगे, जिसमें संख्याओं का प्रत्येक जोड़ा a[2i] है, a[2i+1 ] क्रमशः शीर्षों a[2i] और a[2i+1] के बीच एक ग्राफ किनारे निर्दिष्ट करता है।
इस रिकॉर्डिंग प्रारूप में इस बारे में जानकारी नहीं है कि ग्राफ़ निर्देशित है या नहीं (दोनों विकल्प संभव हैं)। डिग्राफ प्रारूप का उपयोग करते समय, किनारे को a[2i] से a[2i+1] की ओर निर्देशित माना जाता है। यहां और नीचे: अप्रत्यक्ष ग्राफ़ के लिए, यदि आवश्यक हो, तो शीर्षों को रिकॉर्ड करने के क्रम की आवश्यकताएं लागू की जा सकती हैं (उदाहरण के लिए, निर्दिष्ट संख्या के निचले मान वाला शीर्ष पहले आता है)।

C++ में, std::vector का उपयोग करके एक आसन्न वेक्टर निर्दिष्ट करने की सलाह दी जाती है, इसलिए इस डेटा संरचना का नाम है।

केस (ए2): अभारित ग्राफ, किनारे का भार पूर्णांक है

केस (a1) के अनुरूप, हम पूर्णांक किनारे वाले भारित ग्राफ़ के लिए आसन्नता वेक्टर को संख्याओं का एक क्रमबद्ध सेट (गतिशील सरणी) कहते हैं (a[3i], a[3i+1], a[3i+2], ..., जहां i को c 0 क्रमांकित किया गया है), जहां a[3i], a[3i+1], a[3i+2] संख्याओं का प्रत्येक "ट्रिप्लेट" a[3i] क्रमांकित शीर्षों के बीच ग्राफ के एक किनारे को निर्दिष्ट करता है। और a[3i+1], क्रमशः, और मान a [3i+2] इस किनारे का वजन है। ऐसा ग्राफ या तो निर्देशित हो सकता है या नहीं।

केस (बी): अभारित ग्राफ, गैर-पूर्णांक किनारा भार

चूँकि विषम तत्वों को एक सरणी (वेक्टर) में संग्रहीत करना असंभव है, उदाहरण के लिए, निम्नलिखित कार्यान्वयन संभव है। ग्राफ़ को वैक्टर की एक जोड़ी में संग्रहित किया जाता है, जिसमें पहला वेक्टर वज़न निर्दिष्ट किए बिना ग्राफ़ का आसन्न वेक्टर होता है, और दूसरे वेक्टर में संबंधित वज़न होता है (C++ के लिए संभावित कार्यान्वयन: std::pair ). इस प्रकार, पहले वेक्टर के सूचकांक 2i, 2i+1 के तहत शीर्षों की एक जोड़ी द्वारा परिभाषित किनारे के लिए, वजन दूसरे वेक्टर के सूचकांक i के तहत तत्व के बराबर होगा।

खैर, यह क्यों जरूरी है?

खैर, इन पंक्तियों के लेखक ने इसे कई समस्याओं के समाधान के लिए काफी उपयोगी पाया। खैर, औपचारिक दृष्टिकोण से, निम्नलिखित फायदे होंगे:

• आसन्न वेक्टर, किसी भी अन्य "गणनात्मक" संरचना की तरह, काफी कॉम्पैक्ट है, आसन्न मैट्रिक्स (विरल ग्राफ़ के लिए) की तुलना में कम मेमोरी लेता है, और इसे लागू करना अपेक्षाकृत आसान है।
• सिद्धांत रूप में, ग्राफ़ के शीर्षों को ऋणात्मक संख्याओं से भी चिह्नित किया जा सकता है। यदि ऐसी "विकृति" की आवश्यकता हो तो क्या होगा?
• ग्राफ़ में विभिन्न भार (सकारात्मक, नकारात्मक, यहां तक ​​कि शून्य) के साथ कई किनारे और कई लूप हो सकते हैं। यहां कोई प्रतिबंध नहीं है.
• आप किनारों को अलग-अलग गुण भी निर्दिष्ट कर सकते हैं - लेकिन उस पर अधिक जानकारी के लिए, अनुभाग 4 देखें।

हालाँकि, यह स्वीकार किया जाना चाहिए कि यह "सूची" किनारे तक त्वरित पहुंच का संकेत नहीं देती है। और यहां एसोसिएटिव एडजेंसी ऐरे बचाव के लिए आता है, जिसकी चर्चा नीचे की गई है।

3.2 साहचर्य आसन्न सरणी

इसलिए, यदि किसी विशिष्ट किनारे, उसके वजन और अन्य गुणों तक पहुंच हमारे लिए महत्वपूर्ण है, और मेमोरी आवश्यकताएं हमें आसन्न मैट्रिक्स का उपयोग करने की अनुमति नहीं देती हैं, तो आइए सोचें कि हम इस समस्या को हल करने के लिए आसन्न वेक्टर को कैसे बदल सकते हैं। तो, कुंजी ग्राफ़ का एक किनारा है, जिसे पूर्णांकों की क्रमित जोड़ी के रूप में निर्दिष्ट किया जा सकता है। यह किसकी तरह दिखता है? क्या यह सहयोगी सरणी में एक कुंजी नहीं है? और, यदि हां, तो हम इसे लागू क्यों नहीं करते? आइए हमारे पास एक सहयोगी सरणी है जहां प्रत्येक कुंजी - पूर्णांकों की एक क्रमबद्ध जोड़ी - एक मान से जुड़ी होगी - एक पूर्णांक या एक वास्तविक संख्या जो किनारे के वजन को निर्दिष्ट करती है। C++ में, इस संरचना को std::map कंटेनर (std::map) के आधार पर लागू करने की सलाह दी जाती है , int> या std::map , डबल>), या std::multimap यदि एकाधिक किनारे अपेक्षित हैं। ठीक है, हमारे पास ग्राफ़ को संग्रहीत करने के लिए एक संरचना है जो "मैट्रिक्स" संरचनाओं की तुलना में कम मेमोरी लेती है, कई लूप और किनारों के साथ ग्राफ़ को परिभाषित कर सकती है, और शीर्ष संख्याओं की गैर-नकारात्मकता के लिए सख्त आवश्यकताएं भी नहीं हैं (मुझे नहीं पता) इसकी आवश्यकता किसे है, लेकिन फिर भी)।

4. डेटा संरचनाएं भरी हुई हैं, लेकिन कुछ गायब है

और यह सच है: कई समस्याओं को हल करते समय, हमें ग्राफ़ के किनारों पर कुछ विशेषताओं को निर्दिष्ट करने और तदनुसार, उन्हें संग्रहीत करने की आवश्यकता हो सकती है। यदि इन विशेषताओं को स्पष्ट रूप से पूर्णांकों में कम करना संभव है, तो आसन्न वेक्टर और सहयोगी आसन्न सरणी के विस्तारित संस्करणों का उपयोग करके ऐसे "अतिरिक्त सुविधाओं वाले ग्राफ़" को संग्रहीत करना संभव है।

तो, आइए हमारे पास एक अभारित ग्राफ़ है, जिसके प्रत्येक किनारे के लिए, उदाहरण के लिए, पूर्णांकों द्वारा निर्दिष्ट 2 अतिरिक्त सुविधाओं को संग्रहीत करना आवश्यक है। इस मामले में, इसके आसन्न वेक्टर को "जोड़े" के नहीं बल्कि पूर्णांकों के "चौकड़ी" (a[2i], a[2i+1], a[2i+2], a) के क्रमबद्ध सेट के रूप में परिभाषित करना संभव है। [2i+3]…) , जहां a[2i+2] और a[2i+3] संबंधित किनारे की विशेषताओं को निर्धारित करेंगे। किनारों के पूर्णांक भार वाले ग्राफ़ के लिए, क्रम आम तौर पर समान होता है (केवल अंतर यह होगा कि विशेषताएँ किनारे के वजन का पालन करेंगी और तत्वों a[2i+3] और a[2i+4] द्वारा निर्दिष्ट की जाएंगी , और किनारे पर ही 4 नहीं, बल्कि 5 क्रमित संख्याएं निर्दिष्ट की जाएंगी)। और गैर-पूर्णांक किनारे भार वाले ग्राफ़ के लिए, सुविधाओं को इसके अभारित घटक में लिखा जा सकता है।

पूर्णांक किनारे भार वाले ग्राफ़ के लिए एक सहयोगी आसन्न सरणी का उपयोग करते समय, एक मान के रूप में एक संख्या निर्दिष्ट करना संभव नहीं है, लेकिन संख्याओं की एक सरणी (वेक्टर) जो किनारे के वजन के अलावा, इसके अन्य सभी आवश्यक निर्दिष्ट करती है विशेषताएँ। उसी समय, गैर-पूर्णांक भार के मामले में एक असुविधा एक फ्लोटिंग पॉइंट नंबर के साथ एक संकेत निर्दिष्ट करने की आवश्यकता होगी (हां, यह एक असुविधा है, लेकिन यदि ऐसे कई संकेत नहीं हैं, और यदि आप ऐसा नहीं करते हैं) उन्हें बहुत अधिक "मुश्किल" डबल सेट न करें, तो यह कुछ भी नहीं हो सकता है)। इसका मतलब यह है कि C++ में विस्तारित साहचर्य आसन्न सरणियों को निम्नानुसार परिभाषित किया जा सकता है: std::map , std::vector> या std::map , std::वेक्टर, जिसमें "की-वैल्यू-वेक्टर" में पहला मान किनारे का वजन होगा, और फिर इसकी विशेषताओं के संख्यात्मक पदनाम स्थित होंगे।

साहित्य:

सामान्य रूप से ग्राफ़ और एल्गोरिदम के बारे में:

1. कॉर्मेन, थॉमस एच., लीसेर्सन, चार्ल्स आई., रिवेस्ट, रोनाल्ड एल., स्टीन, क्लिफोर्ड। एल्गोरिदम: निर्माण और विश्लेषण, दूसरा संस्करण: ट्रांस। अंग्रेज़ी से - एम.: विलियम्स पब्लिशिंग हाउस, 2।
2. हरारी फ्रैंक. ग्राफ सिद्धांत। एम.: मीर, 1973.
इन्हीं वेक्टर और आसन्नताओं के साहचर्य सरणी के बारे में लेखक की रिपोर्ट:
3. चेर्नौखोव एस.ए. ग्राफ़ / एसए चेर्नौहोव को प्रस्तुत करने और संग्रहीत करने के तरीकों के रूप में आसन्न वेक्टर और सहयोगी आसन्न सरणी। एक ग्राफ का प्रतिनिधित्व करने के लिए डेटा संरचनाओं के रूप में आसन्न वेक्टर और आसन्न मानचित्र // अंतर्राष्ट्रीय वैज्ञानिक और व्यावहारिक सम्मेलन के लेखों का संग्रह "अभिनव विकास के परिणामों को लागू करने की समस्याएं और उन्हें हल करने के तरीके" (सेराटोव, 14.09.2019 सितंबर, 2019)। - स्टरलिटमैक: एएमआई, 65, पी। 69-XNUMX
विषय पर उपयोगी ऑनलाइन स्रोत:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

स्रोत: www.habr.com