सी ++ प्रोग्राम लिंक्ड लिस्ट का उपयोग करके ग्राफ का प्रतिनिधित्व करने के लिए

एक ग्राफ की घटना मैट्रिक्स स्मृति में संग्रहीत करने के लिए एक ग्राफ का एक और प्रतिनिधित्व है। यह मैट्रिक्स एक वर्ग मैट्रिक्स नहीं है। आपतन मैट्रिक्स का क्रम V x E है। जहाँ V शीर्षों की संख्या है और E ग्राफ़ में किनारों की संख्या है।

इस मैट्रिक्स की प्रत्येक पंक्ति में हम कोने रख रहे हैं, और प्रत्येक कॉलम में किनारों को रखा गया है। इस निरूपण में एक किनारे e {u, v} के लिए, इसे कॉलम e के स्थान u और v के लिए 1 से चिह्नित किया जाएगा।

आसन्नता मैट्रिक्स प्रतिनिधित्व की जटिलता

• घटना मैट्रिक्स प्रतिनिधित्व O(V x E) स्थान लेता है जबकि इसकी गणना की जाती है। पूर्ण ग्राफ के लिए किनारों की संख्या V(V-1)/2 होगी। इसलिए आपतन मैट्रिक्स मेमोरी में अधिक जगह लेता है।

इनपुट:

आउटपुट:

एल्गोरिदम

add_edge(adj_list, u, v)

इनपुट - किनारे का u और v {u,v}, और आसन्नता सूची

आउटपुट − ग्राफ़ G की आसन्नता सूची

Begin
   Append v into the list at index u
   Append u into the list at index v
End

उदाहरण कोड

#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
   for(int i = 0; i<v; i++) {
      cout << i << "--->";
      list<int> :: iterator it;
      for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
         cout << *it << " ";
      }
      cout << endl;
   }
}
void add_edge(list<int> adj_list[], int u, int v) {    //add v into the list u, and u into list v
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   //create an array of lists whose size is 6
   list<int> adj_list[v];
   add_edge(adj_list, 0, 4);
   add_edge(adj_list, 0, 3);
   add_edge(adj_list, 1, 2);
   add_edge(adj_list, 1, 4);
   add_edge(adj_list, 1, 5);
   add_edge(adj_list, 2, 3);
   add_edge(adj_list, 2, 5);
   add_edge(adj_list, 5, 3);
   add_edge(adj_list, 5, 4);
   displayAdjList(adj_list, v);
}

आउटपुट

0--->4 3
1--->2 4 5
2--->1 3 5
3--->0 2 5
4--->0 1 5
5--->1 2 3 4