En graf er et sett med vertices som er koblet sammen med edges. De to standard representasjonene er adjacency list (hver vertex lagrer sine naboer) og adjacency matrix (et V×V rutenett med boolske verdier). Valget avhenger av graf density.
En graf er et sett med vertices som er koblet sammen med edges. De to standard representasjonene er adjacency list (hver vertex lagrer sine naboer) og adjacency matrix (et V×V rutenett med boolske verdier). Valget avhenger av graf density.
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]
# 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
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Plass | O(V + E) | O(V²) |
| Edge eksisterer? | O(degree) | O(1) |
| Iterer naboer | O(degree) | O(V) |
| Best for | sparse grafer | dense grafer |
De fleste virkelige grafer (sosiale nettverk, veikart, dependency grafer) er sparse, så adjacency lists sparer enormt med plass og akselererer traverseringer som BFS/DFS.
Å kjenne til trade-off-en lar deg velge representasjonen som holder graf-algoritmene dine effektive i stedet for ved et uhell å bruke O(V²) minne.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner