En graf er et sæt af hjørner forbundet af kanter. De to standard repræsentationer er nabolisten (hvert hjørne gemmer sine naboer) og nabomatricen (et V×V gitter af boolske værdier). Valget afhænger af grafens tæthed.
En graf er et sæt af hjørner forbundet af kanter. De to standard repræsentationer er nabolisten (hvert hjørne gemmer sine naboer) og nabomatricen (et V×V gitter af boolske værdier). Valget afhænger af grafens tæthed.
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
| Naboliste | Naboømatrice | |
|---|---|---|
| Plads | O(V + E) | O(V²) |
| Kant eksisterer? | O(degree) | O(1) |
| Iterer naboer | O(degree) | O(V) |
| Bedst til | sparsomme grafer | tætte grafer |
De fleste grafer i den virkelige verden (sociale netværk, vejkort, afhængighedsgrafer) er sparsomme, så nabolister sparer enormt med plads og fremskynder traversals som BFS/DFS.
At kende kompromisset giver dig mulighed for at vælge den repræsentation, der holder dine grafalgoritmier effektive i stedet for utilsigtet at bruge O(V²) hukommelse.