Unawakilaje grafu: orodha ya jibu au matrix ya jibu?

Question

Accepted Answer

**Grafu** ni seti ya **nodi** zilizounganishwa na **kingo**. Maamuzi mawili ya kawaida ni **orodha ya jibu** (kila nodi huhifadhi jibu lake) na **matrix ya jibu** (gridi ya V×V ya thamani za boolean). Chaguo linategemea **uzani** wa grafu.

## Fomu mbili

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

## Kod

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

## Kulinganisha (V nodi, E kingo)

| | Orodha ya jibu | Matrix ya jibu |
|---|---|---|
| Nafasi | O(V + E) | O(V²) |
| Kingo ipo? | O(degree) | O(1) |
| Kuruka jibu | O(degree) | O(V) |
| Bora kwa | grafu nyinyi | grafu nene |

## Kwa nini ina umuhimu

Grafu nyingi za ulimwengu halisi (mitandao ya kijamii, ramani za barabara, grafu ya utegemezi) ni **nyinyi**, kwa hivyo orodha ya jibu inaokoa nafasi kubwa na kuharakisha traversals kama BFS/DFS.

Kujua kilipuka hiki kukuruhusu kuchagua uwakilishi unaofikia algorithms ya grafu kuwa ya ufanisi badala ya kuakamatia kutumia O(V²) kumbukumbu.

	Orodha ya jibu	Matrix ya jibu
Nafasi	O(V + E)	O(V²)
Kingo ipo?	O(degree)	O(1)
Kuruka jibu	O(degree)	O(V)
Bora kwa	grafu nyinyi	grafu nene