Kako predstavljate graf: lista susjedstva u odnosu na matricu susjedstva?

Question

IT Interview Practice · Accepted Answer

**Graf** je skup **vrhova** povezanih **bridovima**. Dva standardna prikaza su **lista susjedstva** (svaki vrh sprema svoje susjede) i **matrica susjedstva** (V×V mreža logičkih vrijednosti). Izbor ovisi o **gustoći** grafa.

## Dva oblika

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

## Usporedba (V vrhova, E bridova)

| | Lista susjedstva | Matrica susjedstva |
|---|---|---|
| Prostor | O(V + E) | O(V²) |
| Postoji li brid? | O(stupanj) | O(1) |
| Iteracija susjeda | O(stupanj) | O(V) |
| Najbolje za | rijetke grafove | guste grafove |

## Zašto je važno

Većina stvarnih grafova (društvene mreže, cestovne mape, grafikoni ovisnosti) su **rijetke**, tako da liste susjedstva štede ogroman prostor i ubrzavaju prolaze poput BFS/DFS.

Znanje o kompromisu omogućava vam da odaberete prikaz koji čini vaše graf algoritme učinkovitima umjesto da slučajno koristite O(V²) memorije.

	Lista susjedstva	Matrica susjedstva
Prostor	O(V + E)	O(V²)
Postoji li brid?	O(stupanj)	O(1)
Iteracija susjeda	O(stupanj)	O(V)
Najbolje za	rijetke grafove	guste grafove

Dva oblika

Kod

Usporedba (V vrhova, E bridova)

Zašto je važno

Povezana pitanja