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

सभी को नमस्कार।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 आसन्न सदिश

केस (A1): अनवीटेड काउंट

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

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

केस (a2): अनवीटेड ग्राफ, पूर्णांक एज वेट

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

केस (बी): अनवीटेड ग्राफ, नॉन-पूर्णांक एज वेट

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

खैर, यह क्यों आवश्यक है?

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

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

हालाँकि, मुझे स्वीकार करना चाहिए, यह "लिस्टोट" रिब के लिए त्वरित पहुँच प्रदान नहीं करता है। और यहाँ साहचर्य आसन्न सरणी मदद करने के लिए, जिसके बारे में - नीचे।

3.2 सहयोगी आसन्न सरणी

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

4. कम से कम "बाढ़" डेटा संरचनाएं, लेकिन कुछ गायब है

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

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

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

संदर्भ:

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

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