एक ग्राफ की आसन्न सूची प्रतिनिधित्व लिंक्ड सूची प्रतिनिधित्व है। इस निरूपण में हमारे पास सूचियों की एक सरणी है सरणी का आकार 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