آپ ایک گراف کی نمائندگی کیسے کرتے ہیں: adjacency list بمقابلہ adjacency matrix؟

Question

Accepted Answer

ایک **graph** **vertices** کا ایک مجموعہ ہے جو **edges** سے منسلک ہوتے ہیں۔ دو معیاری نمائندگیاں **adjacency list** ہیں (ہر vertex اپنے neighbors کو محفوظ کرتا ہے) اور **adjacency matrix** (V×V بولین کا ایک گرڈ)۔ انتخاب گراف **density** پر منحصر ہے۔

## دونوں شکلیں

```text
Graph:  0 - 1
        |   |
        2 - 3

Adjacency list:          Adjacency matrix:
0: [1, 2]                    0 1 2 3
1: [0, 3]                 0 [0 1 1 0]
2: [0, 3]                 1 [1 0 0 1]
3: [1, 2]                 2 [1 0 0 1]
                          3 [0 1 1 0]
```

## Code

```python
# Adjacency list (dict of lists) — preferred for sparse graphs
adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
neighbors = adj[1]            # O(1) to get a vertex's neighbors

# Adjacency matrix
matrix = [[0]*4 for _ in range(4)]
matrix[0][1] = matrix[1][0] = 1
has_edge = matrix[0][1] == 1  # O(1) edge lookup
```

## موازنہ (V vertices، E edges)

| | Adjacency list | Adjacency matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Edge exists? | O(degree) | O(1) |
| Iterate neighbors | O(degree) | O(V) |
| Best for | sparse graphs | dense graphs |

## یہ کیوں اہم ہے

زیادہ تر حقیقی دنیا کے گرافس (social networks، road maps، dependency graphs) **sparse** ہوتے ہیں، اس لیے adjacency lists بہت زیادہ space بچاتے ہیں اور BFS/DFS جیسے traversals کو تیز کرتے ہیں۔
	radeoff کو جاننا آپ کو ایسی نمائندگی منتخب کرنے کی اجازت دیتا ہے جو آپ کے گراف algorithms کو موثر رکھے بجائے اس کے کہ غیر ارادی طور پر O(V²) memory استعمال کریں۔

	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
Edge exists?	O(degree)	O(1)
Iterate neighbors	O(degree)	O(V)
Best for	sparse graphs	dense graphs