सी ++ प्रोग्राम आसन्न सूची का उपयोग करके ग्राफ़ का प्रतिनिधित्व करने के लिए

एक ग्राफ की आसन्न सूची प्रतिनिधित्व लिंक्ड सूची प्रतिनिधित्व है। इस निरूपण में हमारे पास सूचियों की एक सरणी है सरणी का आकार V है। यहाँ V शीर्षों की संख्या है। दूसरे शब्दों में, हम कह सकते हैं कि हमारे पास विभिन्न सूचियों के V नंबर को संग्रहीत करने के लिए एक सरणी है। यदि कोई सूची शीर्षलेख u वर्टेक्स है, तो यह दर्शाता है कि यह u के सभी आसन्न शीर्षों को धारण करेगा।

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

• यह प्रतिनिधित्व अप्रत्यक्ष ग्राफ के लिए O(V+2E) लेता है, और निर्देशित ग्राफ के लिए O(V+E) लेता है। यदि किनारों की संख्या बढ़ा दी जाती है, तो आवश्यक स्थान भी बढ़ जाएगा।

इनपुट:

आउटपुट:

एल्गोरिदम

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