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 [ i ] [ j ] = 1 तब होता है, जब Vertex i से Vertex j के बीच Edge मौजूद हो, और A [ i ] [ j ] = 0 तब होता है, जब Edge मौजूद न हो।
Weighted Graph में इसी स्थान पर Edge का Weight store किया जाता है।”
- graph sparse हो या dense, matrix size fix रहता है। इसलिए इसे static representation भी कहते हैं।
Structure
- If edge exists → A [ i ] [ j ] = 1
- If no edge → A [ i ] [ j ] = 0
- For weights → A [ i ] [ j ] = 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 –
- हर vertex के साथ एक linked list, dynamic array या vector होती है
- Directed graph में edges सिर्फ एक दिशा में store होते हैं
- Undirected graph में दो entries करनी होती हैं
Graph Example (Simple Undirected Graph)
Vertices : A, B, C, D
Edges :
- 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 :
Example :
Vertices : A, B, C
Edges :
- 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 |
