Kaip tu atstovauti grafą: gretimų sąrašą arba gretimų matricą?

Question

Accepted Answer

**Grafas** yra **viršūnių** rinkinys, sujungtas **briaunomis**. Du standartiniai atvaizdavimo būdai yra **gretimų sąrašas** (kiekviena viršūnė saugo savo kaimynus) ir **gretimų matrica** (V×V loginių reikšmių tinklelis). Pasirinkimas priklauso nuo **grafo tankio**.

## Dvi formos

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

## Palyginimas (V viršūnės, E briaunos)

| | Gretimų sąrašas | Gretimų matrica |
|---|---|---|
| Vieta | O(V + E) | O(V²) |
| Ar briauna egzistuoja? | O(laipsnis) | O(1) |
| Kartoti kaimynus | O(laipsnis) | O(V) |
| Geriausia | retais grafams | tankiems grafams |

## Kodėl tai svarbu

Dauguma realaus pasaulio grafų (socialiniai tinklai, kelio žemėlapiai, priklausomybės grafai) yra **retai**, todėl gretimų sąrašai sutaupo didžiulę atmintį ir pagreitina šurmutus tokius kaip BFS/DFS.

Žinodami kompromisą, galite pasirinkti atvaizdavimą, kuris daro jūsų grafo algoritmus efektyvius, vietoj to, kad netyčia naudosite O(V²) atmintį.

	Gretimų sąrašas	Gretimų matrica
Vieta	O(V + E)	O(V²)
Ar briauna egzistuoja?	O(laipsnis)	O(1)
Kartoti kaimynus	O(laipsnis)	O(V)
Geriausia	retais grafams	tankiems grafams