Hur representerar du en graf: närhetslista eller närhetkmatris?

Question

Accepted Answer

En **graf** är en mängd **noder** anslutna med **kanter**. De två standardrepresentationerna är **närhetslistan** (varje nod lagrar sina grannar) och **närhetkmatrisen** (ett V×V rutnät av booleska värden). Valet beror på grafens **densitet**.

## De två formerna

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

## Jämförelse (V noder, E kanter)

| | Närhetslista | Närhetkmatris |
|---|---|---|
| Utrymme | O(V + E) | O(V²) |
| Kanten finns? | O(degree) | O(1) |
| Iterera grannar | O(degree) | O(V) |
| Bäst för | glesa grafer | täta grafer |

## Varför det är viktigt

De flesta verkliga grafer (sociala nätverk, vägar, beroendegrader) är **glesa**, så närhetstlistor sparar enorm plats och snabbar upp traverseringar som BFS/DFS.

Att kunna denna avvägning gör att du kan välja representationen som håller dina grafalgoritmiska effektiva istället för att av misstag använda O(V²) minne.

	Närhetslista	Närhetkmatris
Utrymme	O(V + E)	O(V²)
Kanten finns?	O(degree)	O(1)
Iterera grannar	O(degree)	O(V)
Bäst för	glesa grafer	täta grafer