ग्राफहरू भण्डारण गर्नका लागि डाटा संरचनाहरू: अवस्थित र दुई "लगभग नयाँ" को समीक्षा

सबैलाई नमस्कार।

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

त्यसैले, सुरु गरौं। तर सुरुदेखि नै होइन - मलाई लाग्छ हामी सबैलाई पहिले नै थाहा छ कि ग्राफ के हो र तिनीहरू के हुन् (निर्देशित, अनिर्देशित, भारित, अभारित, धेरै किनाराहरू र लूपहरू बिना)।

त्यसोभए, जाऔं। हामीसँग "ग्राफ भण्डारण" को लागी डाटा संरचना को लागी के विकल्प छ?

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

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

1.2 घटना म्याट्रिक्स। यस अवस्थामा, हाम्रो ग्राफ पनि तालिकामा भण्डार गरिएको छ, जसमा, नियमको रूपमा, पङ्क्ति संख्याहरू यसको ठाडो संख्याहरूसँग मेल खान्छ, र स्तम्भ संख्याहरू पूर्व-संख्या गरिएका किनारहरूसँग मेल खान्छ। यदि एक vertex र एक किनारा एकअर्कासँग घटना हो भने, त्यसपछि एक गैर-शून्य मान सम्बन्धित कक्षमा लेखिएको छ (अनिर्देशित ग्राफहरूको लागि, 1 लेखिन्छ यदि शीर्ष र किनारा घटना हो भने, उन्मुख ग्राफहरूको लागि - "1" यदि किनारा vertex बाट "निकास" र "-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],..., जहाँ i लाई 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 अन्तर्गतको तत्व बराबर हुनेछ।

खैर, यो किन आवश्यक छ?

ठीक छ, यी रेखाहरूको लेखकले धेरै समस्याहरू समाधान गर्नका लागि यो धेरै उपयोगी पाए। ठीक छ, औपचारिक दृष्टिकोणबाट, त्यहाँ निम्न फाइदाहरू हुनेछन्:

• आसन्न भेक्टर, कुनै पनि अन्य "गणनात्मक" संरचना जस्तै, एकदम कम्प्याक्ट छ, आसन्न म्याट्रिक्स (स्पर्श ग्राफहरूको लागि) भन्दा कम मेमोरी लिन्छ, र कार्यान्वयन गर्न अपेक्षाकृत सजिलो छ।
• ग्राफ को ठाडो, सिद्धान्त मा, पनि नकारात्मक संख्या संग चिन्ह लगाउन सकिन्छ। यदि यस्तो "विकृती" आवश्यक छ भने के हुन्छ?
• ग्राफहरूमा विभिन्न तौलहरू (सकारात्मक, ऋणात्मक, शून्य पनि) सहित धेरै किनारहरू र धेरै लूपहरू समावेश हुन सक्छन्। यहाँ कुनै प्रतिबन्धहरू छैनन्।
• तपाईं किनारहरूमा विभिन्न गुणहरू पनि तोक्न सक्नुहुन्छ - तर त्यसमा थपका लागि, खण्ड ४ हेर्नुहोस्।

यद्यपि, यो स्वीकार गर्नुपर्छ कि यो "सूची" ले किनारामा द्रुत पहुँचलाई संकेत गर्दैन। र यहाँ एसोसिएटिभ एडजेन्सी एरे उद्धारमा आउँछ, जुन तल छलफल गरिएको छ।

3.2 एसोसिएटिभ आसन्न एरे

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

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, जसमा "key-value-vector" मा पहिलो मान किनाराको वजन हुनेछ, र त्यसपछि यसको विशेषताहरूको संख्यात्मक पदनामहरू अवस्थित छन्।

साहित्य:

सामान्य मा ग्राफ र एल्गोरिदम बारे:

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

स्रोत: www.habr.com