ਤੁਸ ਇੱਕ ਗ੍ਰਾਫ ਨੂੰ ਕਿਵੇਂ ਦਰਸਾਉਂਦੇ ਹੋ: adjacency list vs adjacency matrix?

Question

Accepted Answer

ਇੱਕ **graph** **vertices** ਦਾ ਇੱਕ ਸੈਟ ਹੈ ਜੋ **edges** ਦੁਆਰਾ ਜੁੜੇ ਹੁੰਦੇ ਹਨ। ਦੋ ਮਾਨਕ ਪ੍ਰਸਤੁਤੀਆਂ ਹਨ **adjacency list** (ਹਰੇਕ vertex ਆਪਣੇ ਗੁਆਂਢੀਆਂ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ) ਅਤੇ **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]
```

## ਕੋਡ

```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 |

## ਇਹ ਕਿਉਂ ਮਹੱਤਵਪੂਰਨ ਹੈ

ਬਹੁਤੇ ਵਾਸਤਵਿਕ-ਸੰਸਾਰ ਦੇ graphs (ਸਮਾਜਿਕ ਨੈੱਟਵਰਕ, ਰੋਡ ਮੈਪ, ਨਿਰਭਰਤਾ graphs) **sparse** ਹੁੰਦੇ ਹਨ, ਇਸਲਈ adjacency lists ਬਹੁਤ ਸਾਰੀ ਮੈਮੋਰੀ ਬਚਾਉਂਦੇ ਹਨ ਅਤੇ BFS/DFS ਵਰਗੀਆਂ ਟ੍ਰੈਵਰਸਲਾਂ ਨੂੰ ਤੇਜ਼ ਕਰਦੇ ਹਨ।
ਇਸ ਟ੍ਰੇਡ-ਆਫ ਨੂੰ ਜਾਣਨਾ ਤੁਹਾਨੂੰ ਉਹ ਪ੍ਰਸਤੁਤੀ ਚੁਣਨ ਦਿੰਦਾ ਹੈ ਜੋ ਤੁਹਾਡੇ ਗ੍ਰਾਫ ਅਲਗੋਰਿਦਮ ਨੂੰ ਕੁਸ਼ਲ ਰੱਖਦੀ ਹੈ ਬਜਾਏ ਗਲਤੀ ਨਾਲ O(V²) ਮੈਮੋਰੀ ਦੀ ਵਰਤੋਂ ਕਰਨ ਦੇ।

	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