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.
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.
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
| 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 |
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.
Ett bibliotek med IT-intervjufrågor och detaljerade svar — från Junior till Senior.
Donera