algorithm
ग्राफ़

परिचय

टिप्पणियों

सामयिक क्रमबद्ध

एक टोपोलॉजिकल ऑर्डरिंग या एक टोपोलॉजिकल सॉर्ट, एक लाइन पर एक निर्देशित एसाइक्लिक ग्राफ में वर्टिस का आदेश देता है, अर्थात एक सूची में, जैसे कि सभी निर्देशित किनारों को बाएं से दाएं जाता है। यदि ग्राफ़ में एक निर्देशित चक्र शामिल है, तो ऐसा कोई आदेश मौजूद नहीं हो सकता है क्योंकि ऐसा कोई तरीका नहीं है कि आप एक पंक्ति पर सही जा सकते हैं और अभी भी वापस उसी स्थान पर वापस आ सकते हैं जहाँ से आपने शुरू किया था।

औपचारिक रूप से, ग्राफ G = (V, E) , तब इसके सभी लंबों का एक रेखीय क्रम ऐसा होता है कि यदि G में एक किनारे (u, v) ∈ E from (u, v) ∈ E जो वर्टेक्स u से वर्टेक्स v तक होता है v तो u क्रम में v से पूर्व होता है।

यह ध्यान रखना महत्वपूर्ण है कि प्रत्येक डीएजी में कम से कम एक सामयिक प्रकार है।

रैखिक समय में किसी भी DAG के सामयिक क्रम के निर्माण के लिए ज्ञात एल्गोरिदम हैं, एक उदाहरण है:

1. प्रत्येक शीर्ष v लिए परिष्करण बार vf गणना करने के लिए depth_first_search(G) को कॉल करें
2. जैसे ही प्रत्येक शीर्ष समाप्त हो जाता है, इसे एक लिंक्ड सूची के सामने डालें
3. वर्टिकल की लिंक्ड लिस्ट, क्योंकि यह अब सॉर्ट हो गई है।

एक टोपोलॉजिकल सॉर्ट ϴ(V + E) समय में किया जा सकता है, क्योंकि गहराई-पहली खोज एल्गोरिथ्म में ϴ(V + E) समय लगता है और इसमें से प्रत्येक को सम्मिलित करने के लिए Ω(1) (निरंतर समय) लगता है |V| एक लिंक की गई सूची के सामने कोने।

कई एप्लिकेशन घटनाओं के बीच पूर्वनिर्धारितता दर्शाने के लिए निर्देशित एसाइक्लिक ग्राफ का उपयोग करते हैं। हम टोपोलॉजिकल सॉर्टिंग का उपयोग करते हैं ताकि हमें इसके किसी भी उत्तराधिकारी से पहले प्रत्येक शीर्ष को संसाधित करने का आदेश मिले।

एक ग्राफ़ में कार्य प्रदर्शन किए जाने वाले कार्यों का प्रतिनिधित्व कर सकते हैं और किनारों को उन बाधाओं का प्रतिनिधित्व कर सकता है जो एक कार्य को दूसरे से पहले किया जाना चाहिए; एक टोपोलॉजिकल ऑर्डरिंग V में वर्णित कार्यों के कार्यों के सेट को करने के लिए एक वैध अनुक्रम है।

समस्या का उदाहरण और उसका समाधान

एक Task(hours_to_complete: int) v Task(hours_to_complete: int) , अर्थात Task(4) वर्णन करते हैं, जिसमें एक Task वर्णन है जिसे पूरा होने में 4 घंटे लगते हैं, और एक एज e एक Cooldown(hours: int) Cooldown(3) वर्णन करता है, जैसे कि Cooldown(3) अवधि का वर्णन करता है एक पूर्ण कार्य के बाद ठंडा होने का समय।

हमारे ग्राफ को dag कहा जाता है (क्योंकि यह एक निर्देशित चक्रीय ग्राफ है), और इसमें 5 कोने होते हैं:

A <- dag.add_vertex(Task(4)); 
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3)); 
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

जहाँ हम कोने को निर्देशित किनारों से जोड़ते हैं, जैसे कि ग्राफ एक प्रकार का पौधा है,

// A ---> C ----+
// |      |     |
// v      v     v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

तब A और E बीच तीन संभावित सामयिक आदेश हैं,

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E

थोरुप का एल्गोरिथ्म

अप्रत्यक्ष ग्राफ के लिए एकल स्रोत सबसे छोटे रास्ते के लिए थोरूप के एल्गोरिथ्म में दिक् काल से कम समय की जटिलता ओ (एम) है।

मूल विचार निम्नलिखित हैं। (क्षमा करें, मैंने अभी तक इसे लागू करने का प्रयास नहीं किया था, इसलिए मुझे कुछ मामूली विवरण याद आ सकते हैं। और मूल पेपर का भुगतान किया जाता है, इसलिए मैंने इसे संदर्भित करने वाले अन्य स्रोतों से इसे फिर से संगठित करने का प्रयास किया। कृपया इस टिप्पणी को हटा दें यदि आप सत्यापित कर सकते हैं।)

• ओ (एम) में फैले पेड़ को खोजने के तरीके हैं (यहां वर्णित नहीं है)। आपको सबसे कम किनारे से सबसे लंबे समय तक फैले पेड़ को "बढ़ने" की आवश्यकता है, और यह पूरी तरह से विकसित होने वाले कई जुड़े घटकों के साथ एक जंगल होगा।
• पूर्णांक b (b> = 2) का चयन करें और केवल लंबाई सीमा b ^ k के साथ फैले जंगलों पर विचार करें। घटकों को मिलाएं जो बिल्कुल समान हैं लेकिन अलग-अलग k के साथ हैं, और न्यूनतम k को घटक का स्तर कहते हैं। फिर तार्किक रूप से एक पेड़ में घटक बनाते हैं। u, v if का जनक है, u, v से सबसे छोटा घटक है जिसमें पूरी तरह से v सम्‍मिलित है। मूल संपूर्ण ग्राफ है और मूल ग्राफ में पत्तियां एकल वर्टिकल हैं (ऋणात्मक अनन्तता के स्तर के साथ)। पेड़ में अभी भी केवल O (n) नोड्स हैं।
• प्रत्येक घटक की दूरी को स्रोत तक बनाए रखें (जैसे डेज्क्स्ट्रा के एल्गोरिथ्म में)। एक से अधिक कोने वाले घटक की दूरी उसके अनएक्सपैंडेड बच्चों की न्यूनतम दूरी है। स्रोत शीर्ष की दूरी को 0 पर सेट करें और तदनुसार पूर्वजों को अपडेट करें।
• बेस b में दूरियों पर विचार करें। जब पहली बार के स्तर में एक नोड का दौरा करते हैं, तो अपने बच्चों को स्तर कश्मीर के सभी नोड्स (जैसे बाल्टी सॉर्ट में, डिक्स्ट्रा के एल्गोरिथ्म में ढेर की जगह) के द्वारा और उसके दूरी के द्वारा साझा की गई बाल्टियों में डाल दें। हर बार एक नोड पर जाने पर, केवल इसकी पहली बी बाल्टियों पर विचार करें, उनमें से प्रत्येक पर जाएं और हटाएं, वर्तमान नोड की दूरी को अपडेट करें, और नई दूरी का उपयोग करके वर्तमान नोड को अपने स्वयं के माता-पिता को राहत दें और निम्नलिखित के लिए अगली यात्रा की प्रतीक्षा करें बाल्टी।
• जब एक पत्ती का दौरा किया जाता है, तो वर्तमान दूरी शीर्ष की अंतिम दूरी है। मूल ग्राफ़ में इसके सभी किनारों का विस्तार करें और तदनुसार दूरी अपडेट करें।
• रूट नोड (पूरे ग्राफ़) पर बार-बार जाएँ जब तक कि गंतव्य तक न पहुँच जाएँ।

यह इस तथ्य पर आधारित है कि, लंबाई सीमा l के साथ फैले जंगल के दो जुड़े हुए घटकों के बीच l से कम लंबाई के साथ कोई किनारा नहीं है, इसलिए, दूरी x पर शुरू करते हुए, आप केवल एक जुड़े घटक पर ध्यान केंद्रित कर सकते हैं जब तक आप नहीं पहुंचते दूरी x + l। छोटी दूरी के साथ कोने से पहले आप कुछ कोने पर जाएँगे, लेकिन यह कोई फर्क नहीं पड़ता क्योंकि यह ज्ञात है कि यहाँ उन मार्गों से छोटा रास्ता नहीं होगा। अन्य भाग बकेट सॉर्ट / MSD रेडिक्स सॉर्ट की तरह काम करते हैं, और निश्चित रूप से, इसे ओ (एम) फैले पेड़ की आवश्यकता होती है।

डेप्थ फर्स्ट ट्रैवर्सल का उपयोग करके एक निर्देशित ग्राफ में एक चक्र का पता लगाना

यदि DFS के दौरान खोजा गया बैक एज है तो एक निर्देशित ग्राफ में एक चक्र मौजूद है। एक पिछला किनारा नोड से स्वयं या एक पूर्वजों में से एक डीएफएस पेड़ में एक किनारे है। डिस्कनेक्ट किए गए ग्राफ़ के लिए, हमें डीएफएस फ़ॉरेस्ट मिलता है, इसलिए आपको डीएफएस पेड़ों को खोजने के लिए ग्राफ़ में सभी कोने के माध्यम से चलना होगा।

C ++ कार्यान्वयन:

    #include <iostream>
     #include <list>
        
    using namespace std; 
    
    #define NUM_V   4

    bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
    {
        visited[u]=true;
        recStack[u]=true;
        list<int>::iterator i;
        for(i = graph[u].begin();i!=graph[u].end();++i)
        {  
            if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
                return true;
            else if(*i==u) //if there's an edge from the vertex to itself
                return true;
            else if(!visited[*i])
            {   if(helper(graph, *i, visited, recStack))
                   return true;
            }
        }
        recStack[u]=false;
        return false;
    }
    /*
    /The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
    bool isCyclic(list<int> *graph, int V)
    {
      bool visited[V];  //array to track vertices already visited
      bool recStack[V]; //array to track vertices in recursion stack of the traversal.

      for(int i = 0;i<V;i++)
       visited[i]=false, recStack[i]=false;  //initialize all vertices as not visited and not recursed

      for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
      {   if(visited[u]==false)
          {  if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
               return true;
          }
      }
       return false;
    }
    /*
    Driver function
    */
    int main()
    {
        list<int>* graph = new list<int>[NUM_V];
        graph[0].push_back(1);
        graph[0].push_back(2);
        graph[1].push_back(2);
        graph[2].push_back(0);
        graph[2].push_back(3);
        graph[3].push_back(3);
        bool res = isCyclic(graph, NUM_V);
        cout<<res<<endl;
    }

परिणाम: जैसा कि नीचे दिखाया गया है, ग्राफ में तीन बैक एज हैं। शीर्ष 0 और 2 के बीच एक; कोने के बीच 0, 1, और 2; और शीर्ष 3. खोज की समय जटिलता O (V + E) है जहां V, कोने की संख्या है और E किनारों की संख्या है।

ग्राफ सिद्धांत का परिचय

ग्राफ थ्योरी रेखांकन का अध्ययन है, जो गणितीय संरचनाएं हैं जिनका उपयोग वस्तुओं के बीच युग्मक संबंधों को मॉडल करने के लिए किया जाता है।

क्या आप जानते हैं, ग्रह पृथ्वी की लगभग सभी समस्याओं को सड़कों और शहरों की समस्याओं में बदला जा सकता है, और हल किया जा सकता है? कंप्यूटर के आविष्कार से पहले ही कई साल पहले ग्राफ थ्योरी का आविष्कार किया गया था। लियोनहार्ड यूलर ने कोनिग्सबर्ग के सेवन ब्रिज पर एक पेपर लिखा, जिसे ग्राफ थ्योरी का पहला पेपर माना जाता है। तब से, लोगों को यह पता चला है कि अगर हम किसी भी समस्या को इस सिटी-रोड समस्या में बदल सकते हैं, तो हम इसे ग्राफ थ्योरी द्वारा आसानी से हल कर सकते हैं।

ग्राफ थ्योरी में कई अनुप्रयोग हैं। सबसे आम एप्लिकेशन में से एक शहर से दूसरे शहर के बीच सबसे कम दूरी का पता लगाना है। हम सभी जानते हैं कि आपके पीसी तक पहुंचने के लिए, इस वेब-पेज को सर्वर से कई राउटर्स की यात्रा करनी थी। ग्राफ़ थ्योरी से उन राउटरों का पता लगाने में मदद मिलती है जिन्हें पार करने की आवश्यकता होती है। युद्ध के दौरान, किस सड़क को दूसरों से राजधानी शहर को डिस्कनेक्ट करने के लिए बमबारी करने की आवश्यकता होती है, वह भी ग्राफ थ्योरी का उपयोग करके पता लगाया जा सकता है।

चलिए पहले ग्राफ थ्योरी पर कुछ बुनियादी परिभाषाएँ सीखते हैं।

ग्राफ़:

मान लीजिए, हमारे 6 शहर हैं। हम उन्हें 1, 2, 3, 4, 5, 6. के रूप में चिह्नित करते हैं। अब हम उन शहरों को जोड़ते हैं जिनके पास एक-दूसरे के बीच सड़कें हैं।

यह एक सरल ग्राफ है जहां कुछ शहरों को सड़कों से दिखाया गया है जो उन्हें जोड़ रहे हैं। ग्राफ थ्योरी में, हम इनमें से प्रत्येक शहर को नोड या वर्टेक्स कहते हैं और सड़कों को एज कहा जाता है । ग्राफ बस इन नोड्स और किनारों का एक कनेक्शन है।

एक नोड बहुत सी चीजों का प्रतिनिधित्व कर सकता है। कुछ ग्राफ़ में, नोड्स शहरों का प्रतिनिधित्व करते हैं, कुछ हवाई अड्डों का प्रतिनिधित्व करते हैं, कुछ शतरंज में एक वर्ग का प्रतिनिधित्व करते हैं। एज प्रत्येक नोड के बीच संबंध का प्रतिनिधित्व करता है। वह रिश्ता एक हवाई अड्डे से दूसरे हवाई अड्डे तक जाने का समय हो सकता है, एक चौक से दूसरे चौक तक जाने के रास्ते आदि।

शतरंज की बिसात का रास्ता

सरल शब्दों में, एक नोड किसी भी वस्तु का प्रतिनिधित्व करता है और एज दो वस्तुओं के बीच संबंध का प्रतिनिधित्व करता है।

आसन्न नोड:

यदि एक नोड A शेयर नोड बी के साथ एक बढ़त, तो बी ए के निकट माना जाता है। दूसरे शब्दों में, यदि दो नोड्स सीधे जुड़े हुए हैं, तो उन्हें आसन्न नोड्स कहा जाता है। एक नोड में कई आसन्न नोड हो सकते हैं।

निर्देशित और अप्रत्यक्ष ग्राफ़:

निर्देशित रेखांकन में, किनारों पर एक तरफ दिशा के संकेत होते हैं, जिसका अर्थ है कि किनारे यूनिडायरेक्शनल हैं । दूसरी ओर, अप्रत्यक्ष रेखांकन के किनारों पर दोनों तरफ दिशा के संकेत होते हैं, इसका मतलब है कि वे द्विदिश हैं । आमतौर पर अप्रत्यक्ष ग्राफ़ को किनारों के दोनों ओर कोई संकेत नहीं दिया जाता है।

मान लेते हैं कि कोई पार्टी चल रही है। पार्टी में लोगों का प्रतिनिधित्व नोड्स द्वारा किया जाता है और अगर वे हाथ मिलाते हैं तो दो लोगों के बीच एक बढ़त है। तब यह ग्राफ अप्रत्यक्ष है क्योंकि कोई भी व्यक्ति A व्यक्ति B से हाथ मिलाता है यदि और केवल B भी A के साथ हाथ मिलाता है। इसके विपरीत, यदि एक के निहार बी को एक और व्यक्ति बी मेल खाती है के लिए एक व्यक्ति एक से किनारों, तो यह ग्राफ निर्देश दिया जाता है, क्योंकि प्रशंसा जरूरी प्रतिदान नहीं है। पूर्व प्रकार के ग्राफ को अप्रत्यक्ष ग्राफ कहा जाता है और किनारों को अप्रत्यक्ष किनारों कहा जाता है जबकि बाद वाले प्रकार के ग्राफ को निर्देशित ग्राफ कहा जाता है और किनारों को निर्देशित किनारों कहा जाता है।

भारित और वजन रहित ग्राफ़:

एक भारित ग्राफ एक ग्राफ होता है जिसमें प्रत्येक किनारे पर एक संख्या (भार) निर्दिष्ट किया जाता है। इस तरह के वजन हाथ में समस्या के आधार पर उदाहरण लागत, लंबाई या क्षमता के लिए प्रतिनिधित्व कर सकते हैं।

एक अनवेटेड ग्राफ बस विपरीत है। हम मानते हैं कि, सभी किनारों का वजन समान है (संभवतः 1)।

पथ:

एक पथ एक नोड से दूसरे में जाने का एक तरीका दर्शाता है। इसमें किनारों का क्रम होता है। दो नोड्स के बीच कई पथ हो सकते हैं।

ऊपर के उदाहरण में, ए से डी तक दो रास्ते हैं। A-> B, B-> C, C-> D एक मार्ग है। इस रास्ते की लागत 3 + 4 + 2 = 9 है । फिर, एक और रास्ता है A-> D। इस रास्ते की लागत 10 है । जिस मार्ग पर सबसे कम लागत आती है उसे सबसे छोटा मार्ग कहा जाता है ।

डिग्री:

एक शीर्ष की डिग्री किनारों की संख्या है जो इससे जुड़ी हुई हैं। यदि कोई छोर है जो दोनों सिरों (एक लूप) पर शीर्ष से जुड़ता है तो दो बार गिना जाता है।

निर्देशित रेखांकन में, नोड्स में दो प्रकार की डिग्री होती हैं:

• इन-डिग्री: किनारों की संख्या जो नोड को इंगित करती है।
• आउट-डिग्री: किनारों की संख्या जो नोड से अन्य नोड्स की ओर इशारा करती है।

अप्रत्यक्ष रेखांकन के लिए, उन्हें बस डिग्री कहा जाता है।

ग्राफ थ्योरी से संबंधित कुछ एल्गोरिदम

• बेलमैन-फोर्ड एल्गोरिथ्म
• डीजकस्ट्रा का एल्गोरिदम
• Ford-Fulkerson एल्गोरिथ्म
• क्रुसल का एल्गोरिदम
• निकटतम पड़ोसी एल्गोरिथ्म
• प्राइम का एल्गोरिथ्म
• गहराई-पहली खोज
• पहले चौड़ाई खोजो

भंडारण रेखांकन (निकटता मैट्रिक्स)

ग्राफ़ को संग्रहीत करने के लिए, दो विधियाँ सामान्य हैं:

• सहखंडज मैट्रिक्स
• आसन्न सूची

एक आसन्न मैट्रिक्स एक वर्ग मैट्रिक्स है जो एक परिमित ग्राफ का प्रतिनिधित्व करने के लिए उपयोग किया जाता है। मैट्रिक्स के तत्व इंगित करते हैं कि क्या जोड़े के जोड़े ग्राफ़ में आसन्न हैं या नहीं।

समीप का अर्थ है 'बगल में या कुछ और आसपास' या किसी चीज के बगल में होना। उदाहरण के लिए, आपके पड़ोसी आपसे सटे हुए हैं। ग्राफ सिद्धांत में, यदि हम नोड A से नोड B तक जा सकते हैं, तो हम कह सकते हैं कि नोड B नोड A से समीप है। अब हम सीखेंगे कि कैसे स्टोर किया जाए कि कौन से नोड आसन्न मैट्रिक्स के माध्यम से किस से सटे हैं। इसका मतलब है, हम प्रतिनिधित्व करेंगे कि कौन सा नोड उनके बीच बढ़त साझा करता है। यहां मैट्रिक्स का मतलब 2D सरणी है।

यहाँ आप ग्राफ़ के पास एक टेबल देख सकते हैं, यह हमारा आसन्न मैट्रिक्स है। यहाँ मैट्रिक्स [i] [j] = १ दर्शाता है कि i और j के बीच एक धार है। अगर कोई किनारे नहीं है, तो हम बस मैट्रिक्स [i] [j] = 0 डालते हैं।

इन किनारों को भारित किया जा सकता है, जैसे यह दो शहरों के बीच की दूरी का प्रतिनिधित्व कर सकता है। फिर हम 1 डालने के बजाय मैट्रिक्स [i] [j] में मान डालेंगे ।

ग्राफ ऊपर वर्णित है, द्वि-दिशा या अनिर्दिष्ट है इसका मतलब है, अगर हम नोड 2 से नोड 1 पर जा सकते हैं, हम भी नोड से 2 नोड 1 से जा सकते हैं कि। यदि ग्राफ़ को निर्देशित किया गया था, तो ग्राफ के एक तरफ तीर का निशान होता। फिर भी, हम आसन्न मैट्रिक्स का उपयोग करके इसका प्रतिनिधित्व कर सकते हैं।

हम उन नोड्स का प्रतिनिधित्व करते हैं जो अनंत द्वारा बढ़त साझा नहीं करते हैं। एक बात पर गौर किया जाना चाहिए कि, यदि ग्राफ अप्रत्यक्ष है, तो मैट्रिक्स सममित हो जाता है ।

मैट्रिक्स बनाने के लिए छद्म कोड:

Procedure AdjacencyMatrix(N):    //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

हम इस सामान्य तरीके का उपयोग करके मैट्रिक्स को भी आबाद कर सकते हैं:

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                        // E -> number of edges
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

निर्देशित ग्राफ़ के लिए, हम मैट्रिक्स [n2] [n1] = लागत लाइन निकाल सकते हैं।

आसन्न मैट्रिक्स का उपयोग करने की कमियां:

मेमोरी एक बहुत बड़ी समस्या है। कोई फर्क नहीं पड़ता कि कितने किनारे हैं, हमें हमेशा एन * एन आकार के मैट्रिक्स की आवश्यकता होगी जहां एन नोड्स की संख्या है। यदि 10000 नोड्स हैं, तो मैट्रिक्स का आकार 381 मेगाबाइट के आसपास 4 * 10000 * 10000 होगा। यह स्मृति का एक बड़ा अपव्यय है यदि हम उन ग्राफ़ों पर विचार करते हैं जिनमें कुछ किनारे हैं।

मान लीजिए कि हम यह पता लगाना चाहते हैं कि हम नोड यू से किस नोड पर जा सकते हैं। हमें यू की पूरी पंक्ति की जाँच करनी होगी, जिसमें बहुत समय लगता है।

एकमात्र लाभ यह है कि, हम आसानी से यूवी नोड्स और उनके खर्च के बीच के संबंध का पता लगा सकते हैं।

उपर्युक्त छद्म कोड का उपयोग करके जावा कोड लागू:

import java.util.Scanner;
 
public class Represent_Graph_Adjacency_Matrix 
{
    private final int vertices;
    private int[][] adjacency_matrix;
 
    public Represent_Graph_Adjacency_Matrix(int v) 
    {
        vertices = v;
        adjacency_matrix = new int[vertices + 1][vertices + 1];
    }
 
    public void makeEdge(int to, int from, int edge) 
    {
        try 
        {
            adjacency_matrix[to][from] = edge;
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
    }
 
    public int getEdge(int to, int from) 
    {
        try 
        {
            return adjacency_matrix[to][from];
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
        return -1;
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to = 0, from = 0;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Adjacency_Matrix graph;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            graph = new Represent_Graph_Adjacency_Matrix(v);
 
            System.out.println("Enter the edges: <to> <from>");
            while (count <= e) 
            {
                to = sc.nextInt();
                from = sc.nextInt();
 
                graph.makeEdge(to, from, 1);
                count++;
            }
 
            System.out.println("The adjacency matrix for the given graph is: ");
            System.out.print("  ");
            for (int i = 1; i <= v; i++)
                System.out.print(i + " ");
            System.out.println();
 
            for (int i = 1; i <= v; i++) 
            {
                System.out.print(i + " ");
                for (int j = 1; j <= v; j++) 
                    System.out.print(graph.getEdge(i, j) + " ");
                System.out.println();
            }
 
        }
        catch (Exception E) 
        {
            System.out.println("Somthing went wrong");
        }
 
        sc.close();
    }
}

कोड चलाना: फाइल को सेव करें और javac Represent_Graph_Adjacency_Matrix.java का उपयोग करके संकलित करें

उदाहरण:

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
  1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0

भंडारण रेखांकन (आसन्न सूची)

निकटता सूची एक सीमित ग्राफ़ का प्रतिनिधित्व करने के लिए उपयोग की जाने वाली अव्यवस्थित सूचियों का एक संग्रह है। प्रत्येक सूची एक ग्राफ में एक शीर्ष के पड़ोसियों के सेट का वर्णन करती है। ग्राफ़ को संग्रहीत करने में कम मेमोरी लगती है।

चलो एक ग्राफ देखते हैं, और इसके आसन्न मैट्रिक्स:

अब हम इन मूल्यों का उपयोग करके एक सूची बनाते हैं।

इसे आसन्न सूची कहा जाता है। यह दिखाता है कि कौन से नोड किस नोड से जुड़े हैं। हम इस जानकारी को 2D सरणी का उपयोग करके स्टोर कर सकते हैं। लेकिन हमें उसी मेमोरी की कीमत होगी जैसे कि एडिजेन्सी मैट्रिक्स। इसके बजाय हम इसे स्टोर करने के लिए गतिशील रूप से आवंटित मेमोरी का उपयोग करने जा रहे हैं।

कई भाषाएं वेक्टर या सूची का समर्थन करती हैं जिनका उपयोग हम आसन्न सूची को संग्रहीत करने के लिए कर सकते हैं। इनके लिए, हमें सूची का आकार निर्दिष्ट करने की आवश्यकता नहीं है। हमें केवल नोड्स की अधिकतम संख्या निर्दिष्ट करने की आवश्यकता है।

छद्म कोड होगा:

Procedure Adjacency-List(maxN, E):       // maxN denotes the maximum number of nodes
edge[maxN] = Vector()                    // E denotes the number of edges
for i from 1 to E
    input -> x, y                        // Here x, y denotes there is an edge between x, y
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

चूँकि यह एक अप्रत्यक्ष ग्राफ है, यह x से y तक की बढ़त है, y से x तक का किनारा भी है। यदि यह एक निर्देशित ग्राफ था, तो हम दूसरे को छोड़ देंगे। भारित रेखांकन के लिए, हमें लागत भी संग्रहीत करने की आवश्यकता है। हम इन्हें संग्रहीत करने के लिए एक और वेक्टर या लागत नाम की सूची [] बनाएंगे। छद्म कोड:

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

इस एक से, हम आसानी से किसी भी नोड से जुड़े नोड्स की कुल संख्या का पता लगा सकते हैं, और ये नोड क्या हैं। यह निकटता मैट्रिक्स की तुलना में कम समय लेता है। लेकिन अगर हमें यह पता लगाने की जरूरत है कि क्या u और v के बीच एक किनारे है, तो यह आसान होता अगर हम एक आसन्न मैट्रिक्स रखते।