Graph Traversals - Notes

BFS finds shortest paths in unweighted graphs; DFS is useful for connectivity, topological sorts (with modifications).

1
from collections import deque
2
def bfs_shortest(adj, src, dest):
3
  q = deque([src])
4
  dist = {src:0}
5
  while q:
6
    u = q.popleft()
7
    if u == dest: return dist[u]
8
    for v in adj[u]:
9
      if v not in dist:
10
        dist[v] = dist[u] + 1
11
        q.append(v)
12
  return -1

Use BFS for minimum hops, DFS for exploring full components or recursion-based tasks. Sometimes good enough is actually good enough - especially for v1.