Rilasciato · in miglioramento
Guida a Visita dei grafi · 4/6
Per ora questo capitolo è disponibile solo in inglese.
The cost of a graph traversal depends on the number of vertices V, the number of edges E, and how the graph is stored. This chapter analyzes time and space for BFS, DFS and topological sorting, and compares representations and alternative algorithms.
Running BFS or DFS on an adjacency list, two facts hold:
O(V) part.E entries in a directed graph and 2E in an undirected one. That is the O(E) part.So the total is O(V + E). There is no separate best, average or worst case: a full traversal always pays this for the reachable part of the graph. Only an early exit, such as stopping when a target is found, can finish sooner.
With an adjacency matrix, finding a vertex's neighbors means scanning its whole row of V cells, so the traversal becomes O(V^2). For sparse graphs that is a big difference.
from collections import deque
def bfs_matrix(matrix, start):
n = len(matrix)
dist = [-1] * n
dist[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in range(n): # scans all n cells, neighbor or not
if matrix[u][v] and dist[v] == -1:
dist[v] = dist[u] + 1
queue.append(v)
return dist # O(V^2) overallO(V)O(V) in the worst caseO(V) in the worst case (a long chain)O(V + E) as an adjacency list, O(V^2) as a matrix| Operation | Adjacency list | Adjacency matrix | Edge list |
|---|---|---|---|
| Memory | O(V + E) | O(V^2) | O(E) |
| Is (u, v) an edge? | O(deg(u)) | O(1) | O(E) |
| All neighbors of u | O(deg(u)) | O(V) | O(E) |
| Full BFS/DFS | O(V + E) |
O(V^2)O(V + E) after conversion |
For dense graphs, where E approaches V^2 (say a thousand vertices and hundreds of thousands of edges), a matrix is reasonable. Most real-world and interview graphs are sparse, so the adjacency list is the default. If you frequently ask "are u and v adjacent?", store neighbors in a set instead of a list for average O(1) lookups.
An R x C grid has RC vertices and at most four neighbors per cell, so O(RC) edges. Grid BFS takes O(RC) time and space. A 1000 x 1000 grid is a million vertices, and in Python constant factors start to matter: flattening coordinates to a single index (r * C + c) and using flat lists noticeably speeds things up.
| Algorithm | Used for | Time |
|---|---|---|
| BFS | Unweighted shortest paths, layer-by-layer search | O(V + E) |
| DFS | Components, cycles, topological order, backtracking | O(V + E) |
| Kahn's topological sort | DAG ordering, cycle checks | O(V + E) |
| 0-1 BFS | Edge weights of 0 or 1 | O(V + E) |
| Dijkstra (binary heap) | Non-negative weighted shortest paths | O((V + E) log V) |
| Bellman-Ford | Negative weights allowed | O(VE) |
| Floyd-Warshall | All-pairs shortest paths | O(V^3) |
When every edge has the same weight, BFS is both simpler and faster than Dijkstra.
Using a list as a queue makes each pop(0) shift every remaining element, turning BFS into O(V^2).
from collections import deque
import timeit
def drain_list(n):
items = list(range(n))
while items:
items.pop(0) # O(n) each time
def drain_deque(n):
items = deque(range(n))
while items:
items.popleft() # O(1) each time
n = 100_000
print(timeit.timeit(lambda: drain_list(n), number=1))
print(timeit.timeit(lambda: drain_deque(n), number=1))Recursive DFS raises RecursionError once it passes Python's recursion limit (about 1000 by default). You can raise the limit, but overflowing the C stack can crash the process, so deep graphs are safer with an iterative DFS.
import sys
def depth(n):
return 0 if n == 0 else 1 + depth(n - 1)
print(sys.getrecursionlimit()) # usually 1000
try:
depth(5000)
except RecursionError:
print("Recursion too deep; switch to an iterative DFS.")BFS, DFS and topological sorting on an adjacency list all run in O(V + E) time with O(V) extra space. An adjacency matrix makes edge checks instant but traversal O(V^2). In practice, implementation choices such as using a deque and avoiding deep recursion matter as much as the asymptotics.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.