इस ट्यूटोरियल में, आप सीखेंगे कि आसन्न सूची क्या है। साथ ही, आपको C, C ++, Java और पायथन में आसन्न सूची के काम करने के उदाहरण मिलेंगे।
एक सन्निकटन सूची लिंक्ड सूची की एक सरणी के रूप में एक ग्राफ का प्रतिनिधित्व करती है।
सरणी का सूचकांक एक शीर्ष का प्रतिनिधित्व करता है और इसकी लिंक की गई सूची में प्रत्येक तत्व अन्य शीर्षों का प्रतिनिधित्व करता है जो शीर्ष के साथ एक किनारे बनाते हैं।
आसन्न सूची प्रतिनिधित्व
एक ग्राफ और उसके समतुल्य आसन्न सूची प्रतिनिधित्व नीचे दिखाया गया है।
आसन्न सूची प्रतिनिधित्व
भंडारण के संदर्भ में एक आसन्न सूची कुशल है क्योंकि हमें केवल किनारों के लिए मूल्यों को संग्रहीत करने की आवश्यकता है। लाखों कोने और किनारों के साथ विरल ग्राफ के लिए, इसका मतलब बहुत अधिक बचा हुआ स्थान हो सकता है।
आसन्न सूची संरचना
सबसे सरल आसन्न सूची को नोड्स को व्यवस्थित करने के लिए एक शीर्ष और एक ग्राफ डेटा संरचना को संग्रहीत करने के लिए नोड डेटा संरचना की आवश्यकता होती है।
हम एक ग्राफ की मूल परिभाषा के करीब रहते हैं - कोने और किनारों का संग्रह (V, E)। सादगी के लिए, हम एक लेबल वाले के विपरीत एक अप्रकाशित ग्राफ़ का उपयोग करते हैं अर्थात उनके सूचकांकों को 0,1,2,3 द्वारा पहचाना जाता है।
चलो यहाँ खेलने पर डेटा संरचनाओं में खुदाई करते हैं।
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
आप पर struct node** adjListsहावी न होने दें ।
हम कह रहे हैं कि हम एक पॉइंटर को स्टोर करना चाहते हैं struct node*। इसका कारण यह है कि हम यह नहीं जानते हैं कि ग्राफ़ में कितने कोने होंगे और इसलिए हम संकलन समय पर लिंक्ड सूची की एक सरणी नहीं बना सकते।
आसन्न सूची C ++
यह एक ही संरचना है, लेकिन C ++ की इन-बिल्ट सूची STL डेटा संरचनाओं का उपयोग करके, हम संरचना को थोड़ा साफ करते हैं। हम कार्यान्वयन के विवरण को भी सार करने में सक्षम हैं।
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
आसन्न सूची जावा
लिंक्ड लिस्ट की एरियर को स्टोर करने के लिए हम जावा कलेक्शंस का इस्तेमाल करते हैं।
class Graph ( private int numVertices; private LinkedList adjLists(); )
लिंक्डलिस्ट का प्रकार इस बात से निर्धारित होता है कि आप उसमें कौन सा डेटा स्टोर करना चाहते हैं। लेबल ग्राफ के लिए, आप एक शब्दकोश को इंटेगर के बजाय स्टोर कर सकते हैं
आसन्न सूची पायथन
एक कारण है कि पायथन को इतना प्यार मिलता है। कोने और उसके किनारों का एक सरल शब्दकोश एक ग्राफ का पर्याप्त प्रतिनिधित्व है। आप अपने आप को वर्टेक्स को जितना चाहें उतना जटिल बना सकते हैं।
graph = ('A': set(('B', 'C')), 'B': set(('A', 'D', 'E')), 'C': set(('A', 'F')), 'D': set(('B')), 'E': set(('B', 'F')), 'F': set(('C', 'E')))
पायथन, जावा और सी / सी ++ उदाहरण
पायथन जावा सी सी ++ # Adjascency List representation in Python class AdjNode: def __init__(self, value): self.vertex = value self.next = None class Graph: def __init__(self, num): self.V = num self.graph = (None) * self.V # Add edges def add_edge(self, s, d): node = AdjNode(d) node.next = self.graph(s) self.graph(s) = node node = AdjNode(s) node.next = self.graph(d) self.graph(d) = node # Print the graph def print_agraph(self): for i in range(self.V): print("Vertex " + str(i) + ":", end="") temp = self.graph(i) while temp: print(" -> ()".format(temp.vertex), end="") temp = temp.next print(" ") if __name__ == "__main__": V = 5 # Create graph and edges graph = Graph(V) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 2) graph.print_agraph()
// Adjascency List representation in Java import java.util.*; class Graph ( // Add edge static void addEdge(ArrayList am, int s, int d) ( am.get(s).add(d); am.get(d).add(s); ) public static void main(String() args) ( // Create the graph int V = 5; ArrayList am = new ArrayList (V); for (int i = 0; i < V; i++) am.add(new ArrayList()); // Add edges addEdge(am, 0, 1); addEdge(am, 0, 2); addEdge(am, 0, 3); addEdge(am, 1, 2); printGraph(am); ) // Print the graph static void printGraph(ArrayList am) ( for (int i = 0; i < am.size(); i++) ( System.out.println("Vertex " + i + ":"); for (int j = 0; j " + am.get(i).get(j)); ) System.out.println(); ) ) )
// Adjascency List representation in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; ); // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create a graph struct Graph* createAGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); int i; for (i = 0; i adjLists(i) = NULL; return graph; ) // Add edge void addEdge(struct Graph* graph, int s, int d) ( // Add edge from s to d struct node* newNode = createNode(d); newNode->next = graph->adjLists(s); graph->adjLists(s) = newNode; // Add edge from d to s newNode = createNode(s); newNode->next = graph->adjLists(d); graph->adjLists(d) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Vertex %d: ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; )
// Adjascency List representation in C++ #include using namespace std; // Add edge void addEdge(vector adj(), int s, int d) ( adj(s).push_back(d); adj(d).push_back(s); ) // Print the graph void printGraph(vector adj(), int V) ( for (int d = 0; d < V; ++d) ( cout << " Vertex " << d << ":"; for (auto x : adj(d)) cout < " << x; printf(""); ) ) int main() ( int V = 5; // Create a graph vector adj(V); // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); )
