आलेख संचयित करण्यासाठी डेटा संरचना: विद्यमान आणि दोन "जवळजवळ नवीन" चे पुनरावलोकन

नमस्कार.

या नोटमध्ये, मी संगणक विज्ञानात आलेख संग्रहित करण्यासाठी वापरल्या जाणार्‍या मुख्य डेटा स्ट्रक्चर्सची यादी करण्याचे ठरविले आणि मी अशा आणखी काही संरचनांबद्दल देखील बोलेन ज्या माझ्यासाठी "क्रिस्टलीकृत" आहेत.

तर, चला सुरुवात करूया. पण अगदी सुरुवातीपासूनच नाही - मला वाटते की ग्राफ म्हणजे काय आणि ते काय आहेत (दिग्दर्शित, अनिर्देशित, भारित, वजन न केलेले, एकाधिक कडा आणि लूपसह किंवा त्याशिवाय) आपल्या सर्वांना आधीच माहित आहे.

तर चला. आमच्याकडे “ग्राफ स्टोरेज” साठी डेटा स्ट्रक्चर्ससाठी कोणते पर्याय आहेत?

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 संलग्नता वेक्टर

केस (a1): वजन न केलेला आलेख

वजन नसलेल्या आलेखासाठी आपण समसंख्येच्या पूर्णांकांचा क्रमबद्ध संच (a[2i], a[2i+1],..., जेथे मला c 0 क्रमांकित केले आहे) समीप वेक्टर म्हणू, ज्यामध्ये संख्यांची प्रत्येक जोडी a[2i] आहे, a[2i+1] अनुक्रमे a[2i] आणि a[2i+1] शिरोबिंदूंमधील आलेख किनार निर्दिष्ट करते.
या रेकॉर्डिंग फॉरमॅटमध्ये आलेख निर्देशित केला आहे की नाही याबद्दल माहिती नाही (दोन्ही पर्याय शक्य आहेत). डायग्राफ फॉरमॅट वापरताना, किनारा a[2i] ते a[2i+1] कडे निर्देशित केला जातो. येथे आणि खाली: अनिर्देशित आलेखांसाठी, आवश्यक असल्यास, रेकॉर्डिंग शिरोबिंदूंच्या क्रमासाठी आवश्यकता लागू केल्या जाऊ शकतात (उदाहरणार्थ, त्यास नियुक्त केलेल्या संख्येच्या कमी मूल्यासह शिरोबिंदू प्रथम येतो).

C++ मध्ये, std::vector वापरून संलग्नता वेक्टर निर्दिष्ट करणे उचित आहे, म्हणून या डेटा स्ट्रक्चरचे नाव.

केस (a2): वजन न केलेला आलेख, काठाचे वजन पूर्णांक आहेत

केस (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] हे या काठाचे वजन आहे. असा आलेख एकतर निर्देशित केला जाऊ शकतो किंवा नाही.

केस (b): वजन न केलेला आलेख, पूर्णांक नसलेले किनारी वजन

विषम घटक एका अॅरे (वेक्टर) मध्ये संग्रहित करणे अशक्य असल्याने, उदाहरणार्थ, खालील अंमलबजावणी शक्य आहे. आलेख वेक्टरच्या जोडीमध्ये संग्रहित केला जातो, ज्यामध्ये पहिला वेक्टर हा आलेखाचा वेक्टर असतो जो वजन निर्दिष्ट न करता, आणि दुसऱ्या वेक्टरमध्ये संबंधित वजने असतात (C++: std::pair साठी संभाव्य अंमलबजावणी ). अशा प्रकारे, पहिल्या वेक्टरच्या अनुक्रमणिका 2i, 2i+1 अंतर्गत शिरोबिंदूंच्या जोडीने परिभाषित केलेल्या काठासाठी, वजन दुसर्‍या वेक्टरच्या इंडेक्स i अंतर्गत घटकाएवढे असेल.

बरं, हे का आवश्यक आहे?

बरं, या ओळींच्या लेखकाला बर्‍याच समस्या सोडवण्यासाठी उपयुक्त वाटले. बरं, औपचारिक दृष्टिकोनातून, खालील फायदे होतील:

• संलग्नता वेक्टर, इतर कोणत्याही "गणनात्मक" संरचनेप्रमाणे, अगदी संक्षिप्त आहे, संलग्नता मॅट्रिक्स (विरळ आलेखासाठी) पेक्षा कमी मेमरी घेते आणि अंमलबजावणी करणे तुलनेने सोपे आहे.
• आलेखाचे शिरोबिंदू, तत्त्वतः, नकारात्मक संख्यांनी देखील चिन्हांकित केले जाऊ शकतात. अशा "विकृती" आवश्यक असल्यास काय?
• आलेखांमध्ये भिन्न वजनांसह (सकारात्मक, ऋण, अगदी शून्य) अनेक कडा आणि एकाधिक लूप असू शकतात. येथे कोणतेही निर्बंध नाहीत.
• तुम्ही कडांना वेगवेगळे गुणधर्म देखील नियुक्त करू शकता - परंतु त्याबद्दल अधिक माहितीसाठी, विभाग 4 पहा.

तथापि, हे मान्य केले पाहिजे की ही "सूची" काठावर द्रुत प्रवेश सूचित करत नाही. आणि येथे असोसिएटिव्ह अॅडजेसन्सी अॅरे बचावासाठी येतो, ज्याची खाली चर्चा केली आहे.

3.2 सहयोगी संलग्नता अॅरे

म्हणून, जर एखाद्या विशिष्ट काठावर प्रवेश करणे, त्याचे वजन आणि इतर गुणधर्म आपल्यासाठी गंभीर आहेत आणि स्मृती आवश्यकता आपल्याला संलग्नता मॅट्रिक्स वापरण्याची परवानगी देत ​​​​नाही, तर या समस्येचे निराकरण करण्यासाठी आपण संलग्नता वेक्टर कसा बदलू शकतो याचा विचार करूया. तर, की ही आलेखाची एक किनार आहे, जी पूर्णांकांची क्रमबद्ध जोडी म्हणून निर्दिष्ट केली जाऊ शकते. हे कसे दिसते? असोसिएटिव्ह अॅरेमधली ती एक की नाही का? आणि तसे असल्यास, आपण ते का राबवत नाही? आपल्याकडे एक सहयोगी अॅरे असू द्या जिथे प्रत्येक की - पूर्णांकांची क्रमबद्ध जोडी - मूल्याशी संबंधित असेल - पूर्णांक किंवा वास्तविक संख्या जी काठाचे वजन निर्दिष्ट करते. C++ मध्ये, std::map कंटेनर (std::map) वर आधारित ही रचना लागू करण्याचा सल्ला दिला जातो. , int> किंवा std::map , double>), किंवा 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::vector, ज्यामध्ये “की-व्हॅल्यू-व्हेक्टर” मधील पहिले मूल्य काठाचे वजन असेल आणि नंतर त्याच्या वैशिष्ट्यांचे संख्यात्मक पदनाम स्थित असतील.

साहित्य:

सर्वसाधारणपणे आलेख आणि अल्गोरिदम बद्दल:

1. कॉर्मेन, थॉमस एच., लीझरसन, चार्ल्स I., रिव्हेस्ट, रोनाल्ड एल., स्टीन, क्लिफर्ड. अल्गोरिदम: बांधकाम आणि विश्लेषण, दुसरी आवृत्ती: ट्रान्स. इंग्रजीतून - एम.: विल्यम्स पब्लिशिंग हाऊस, 2.
2. हरारी फ्रँक. आलेख सिद्धांत. एम.: मीर, 1973.
या समान वेक्टर आणि संलग्नकांच्या सहयोगी अॅरेबद्दल लेखकाचा अहवाल:
3. चेरनोखोव्ह एस.ए. आलेखांचे प्रतिनिधित्व आणि संग्रहित करण्याचे मार्ग म्हणून संलग्नक वेक्टर आणि सहयोगी संलग्नता अॅरे / एसए चेरनोहॉव्ह. ग्राफचे प्रतिनिधित्व करण्यासाठी डेटा स्ट्रक्चर्स म्हणून संलग्नता वेक्टर आणि संलग्नता नकाशा // आंतरराष्ट्रीय वैज्ञानिक आणि व्यावहारिक परिषदेच्या लेखांचा संग्रह "नवीन घडामोडींचे परिणाम अंमलात आणण्याच्या समस्या आणि त्यांचे निराकरण करण्याचे मार्ग" (सेराटोव्ह, 14.09.2019 सप्टेंबर, 2019). – स्टरलिटामक: AMI, 65, p. ६५-६९
विषयावरील उपयुक्त ऑनलाइन स्रोत:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

स्त्रोत: www.habr.com