adjacency matrix

Graph Representation (परिभाषा) Graph Representation वह तरीका है, जिसके माध्यम से किसी Graph के Vertices (nodes) और Edges (connections) को Computer Memory में व्यवस्थित रूप से Store किया जाता है, जिससे Graph पर विभिन्न Algorithms जैसे - BFS, DFS, Dijkstra, Prim, Kruskal आदि efficiently काम कर सकें। साधारण शब्दों में : Graph को memory में किस रूप में रखा जाए, उसे ही Graph Representation कहते हैं। Graph को represent करने के 3 main types हैं : Adjacency Matrix Adjacency List Incidence Matrix Why Representation Matters? (Representation जरूरी क्यों है?) Graph Representation बहुत महत्वपूर्ण है, क्योंकि Graph को memory में कैसे store किया जाता है, उसी पर उसकी performance, speed और memory usage depend करती है। सही representation चुनने से Graph-based algorithms जैसे - BFS, DFS, Dijkstra, Prim, Kruskal आदि तेज़ी से चल पाते हैं, और पूरे system की efficiency बढ़ जाती है। मुख्य कारण : 1. Memory Efficiency हर Graph का structure अलग होता है : Sparse Graph → कम Edges Dense Graph → बहुत ज्यादा Edges गलत representation चुनने पर memory बहुत waste होती है। 2. Fast Searching & Traversal कुछ operations जैसे - “edge exist करता है या नहीं?” या “vertex के neighbours कौन हैं?” Adjacency Matrix में बहुत fast, लेकिन List में थोड़ा slow होता है।इसलिए representation बदलते ही algorithms की speed भी बदल जाती है। 3. Algorithm Performance Graph Algorithms representation पर heavily depend करते हैं : Adjacency List → BFS/DFS/Dijkstra fastest Matrix → Edge check O(1) अगर representation सही ना हो तो time complexity बहुत बढ़ सकती है। 4. Handling Large Networks Real-life systems जैसे : Google Maps (करोड़ों roads), Facebook Graph (बिलियंस connections), IRCTC Routes इनमें efficient representation ही system को तेज़ रखता है। 5. Data Access Pattern Improve Representation structure के आधार पर CPU caching, memory locality और traversal patterns बेहतर हो जाते हैं, जिससे performance naturally बढ़ती है। 6. Storage Flexibility (Flexible Structure) कुछ Graphs dynamic होते हैं, जिनमें नए Nodes/Edges जोड़ने पड़ते हैं। ऐसी situations में Adjacency List सबसे perfect माना जाता है। Types of graph representations (प्रकार) 1. Adjacency Matrix "Adjacency Matrix एक Square Matrix होती है, जिसमें A 1 तब होता है, जब Vertex i से Vertex j के बीच Edge मौजूद हो, और A 0 तब होता है, जब Edge मौजूद न हो।Weighted Graph में इसी स्थान पर Edge का Weight store किया जाता है।" graph sparse हो या dense, matrix size fix रहता है। इसलिए इसे static representation भी कहते हैं। Structure If edge exists → A 1 If no edge → A 0 For weights → A w (weight) अगर हमारा graph में 5 vertices हैं, तो matrix size होगा : 5 × 5 25 cells Example : मान लीजिए 4 stations हैं : A → B → C → D अगर A से B ट्रेन जाती है, B से C, और C से D, तो matrix कुछ ऐसा होगा : A B C D A 0 1 0 0 B 0 0 1 0 C 0 0 0 1 D 0 0 0 0 इससे instantly पता चलता है, कि कौन-सा station directly किससे connected है। Advantages (लाभ) Edge Checking O(1) — Edge मौजूद है या नहीं, तुरंत पता चलता है। Simple Implementation — बनाना और उपयोग करना आसान। Suitable for Dense Graphs— जब edges बहुत ज्यादा हों। Parallel Computation Friendly — Matrix operations parallel में आसानी से चलते हैं। Disadvantages (हानियाँ) High Memory Usage (O(V²)) — Vertices बढ़ते ही matrix बहुत बड़ी हो जाती है। Space Waste in Sparse Graphs — कम edges होने पर अधिकतर cells खाली रहते हैं। Finding Neighbors Slow (O(V))— एक vertex के सभी neighbours पाने के लिए पूरी row चेक करनी पड़ती है। 2. Adjacency List Adjacency List वह representation है, जिसमें Graph के हर Vertex के लिए एक अलग List बनाई जाती है, जिसमें उस vertex से जुड़े सभी vertices (neighbours) को store किया जाता है। हर vertex की अपनी neighbours की list होती है — यही Adjacency List है। Structure - A → B, C B → A, D C → A, D D → B, C हर vertex के साथ एक linked list, dynamic array या vector होती है Directed graph में edges सिर्फ एक दिशा में store होते हैं Undirected graph में दो entries करनी होती हैं Graph Example (Simple Undirected Graph) Vertices : A, B, C, DEdges : A — B A — C B — D Adjacency List : A → B, C B → A, D C → A D → B Advantages (लाभ) Very memory-efficient, especially sparse graph में BFS, DFS जैसे graph traversal बहुत fast चलते हैं Real-life networks (social networks, transport networks) के लिए उपयुक्त Large datasets पर best performance देता है Disadvantages (हानियाँ) Edge existence check slow (A से B connection है?) → O(k) Implementation adjacency matrix की तुलना में थोड़ा complex Dense graphs में efficient नहीं 3. Incidence Matrix Incidence Matrix एक V × E matrix होती है, जिसमें हर row एक vertex को और हर column एक edge को represent करता है। अगर कोई vertex किसी edge से जुड़ा हो, तो उस cell में 1 (या directed graph में +1 / –1) रखा जाता है, और न जुड़े होने पर 0। Structure : For undirected graph : If vertex i is part of edge e → I 1 Else → I 0 Directed graph में +1 / –1 use होता है direction बताने के लिए। Example : Vertices : A, B, CEdges : e1 A—B e2 B—C e3 A—C Incidence Matrix : e1 e2 e3 A 1 0 1 B 1 1 0 C 0 1 1 Advantages (लाभ) Vertex degree आसानी से पता चलता है Theoretical calculations में helpful Flow networks, circuits, bipartite graphs में अच्छा उपयोग Edge-based operations के लिए easy Disadvantages (हानियाँ) Memory usage ज़्यादा (V × E) Real-life applications में कम practical Algorithms implement करना complex Sparse graphs में भी matrix बड़ी होती है Comparison of Various Types of Graph Representation (तुलनात्मक सारणी) Feature / Basis Adjacency Matrix Adjacency List Incidence Matrix Basic Structure V × V Square Matrix प्रत्येक vertex की neighbours की list V × E Matrix Memory Usage High (O(V²)) Low (O(V + E)) Moderate–High (O(V × E)) Best For Dense Graph Sparse Graph Mathematical/Flow Networks Edge Check Speed Very Fast (O(1)) Slow (O(k)) जहाँ k degree Medium (column scan) Finding Neighbours Slow (Entire row scan) Fast (Direct list) Slow (scan required) Directed Graph Support Yes Yes Yes (+1, –1 notation) Weighted Graph Support Yes (weight stored as entry) Yes (weight stored in list) Yes (edge column stores weight) Ease of Implementation Very Easy Moderate Complex Space Efficiency Poor for large graphs Best for large graphs Poor when edges are many Add/Remove Edge Fast but costly for memory Very Fast (append/remove) Difficult Applications Small graphs, matrix-based algorithms Real-world networks, dynamic graphs Electrical circuits, flow networks, theoretical graph models Symmetry Undirected graphs में symmetric List entries in both directions No symmetry guarantee Degree Calculation Row/column count List length Sum of row entries Algorithm Compatibility Good for Floyd–Warshall Best for BFS, DFS, Dijkstra Theoretical + network flow

Representation of Graph : Adjacency Matrix, List & Incidence Matrix

DCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

Representation of Graph : Adjacency Matrix, List & Incidence Matrix

Start typing and press enter to search

DCA के सभी नोट्स, पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स, पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

DCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर