# Adjacency list — most common for sparse graphsfrom collections import defaultdict
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3)]:
graph[u].append(v)
graph[v].append(u) # undirected
BFS — Breadth-First Search
BFS explores all neighbours at the current depth before going deeper. Uses a queue. Finds shortest path (by edge count) in unweighted graphs.
from collections import deque
defbfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr); queue.append(nbr)
return order # O(V + E)
DFS — Depth-First Search
DFS explores as deep as possible before backtracking. Uses a stack (or recursion). Used for: cycle detection, topological sort, connected components.
defdfs(graph, start, visited=None):
if visited isNone: visited = set()
visited.add(start)
for nbr in graph[start]:
if nbr not in visited:
dfs(graph, nbr, visited)
return visited # O(V + E)
Practice
1. Find the shortest path (in edges) between two nodes using BFS.
def shortest_path(graph, src, dst):
if src == dst: return [src]
visited = {src}
queue = deque([[src]])
while queue:
path = queue.popleft()
for nbr in graph[path[-1]]:
if nbr not in visited:
new_path = path + [nbr]
if nbr == dst: return new_path
visited.add(nbr)
queue.append(new_path)
return None # no path
2. When would you choose DFS over BFS?
Use DFS when: detecting cycles, topological sorting, finding all paths,
solving mazes (depth-first backtracking), checking graph connectivity.
Use BFS when: finding shortest path (unweighted), level-order traversal,
finding all nodes at distance k.
Knowledge Check
Adjacency list is preferred over adjacency matrix for sparse graphs because
Matrix is O(1); list is O(degree) — matrix wins for lookup.
Correct — for sparse graphs E << V², so adjacency list is far more memory-efficient.
Both representations support weighted edges.
For dense graphs (E close to V²), matrix and list have similar space; matrix wins on lookup speed.
Recap: adjacency matrix = O(V²) space. List = O(V+E). For a graph with 1M vertices and 1M edges: matrix = 10¹² cells, list = 2M entries.
BFS uses a queue to
A visited set does that; the queue handles traversal order.
Correct — FIFO order means all distance-k nodes are processed before any distance-(k+1) node.
BFS doesn't sort; it processes in discovery order.
Backtracking is DFS behaviour.
Recap: BFS + queue = shortest path by edge count. All nodes at distance 1 processed before distance 2, etc.
DFS time complexity on a graph with V vertices and E edges is
That's BFS/DFS on an adjacency matrix. With adjacency list it's O(V+E).
Correct — each vertex and each edge is visited exactly once.
That's Dijkstra's complexity.
No sorting involved; DFS is O(V+E).
Recap: BFS and DFS both run in O(V+E) with adjacency lists — you visit every vertex once and follow every edge once.
Which algorithm finds the shortest path in an unweighted graph?
DFS finds A path but not necessarily the shortest one.
Correct — BFS explores by distance, so the first time it reaches a node is via the shortest path.
Dijkstra's handles weighted graphs; BFS suffices (and is simpler) for unweighted.
Bellman-Ford handles negative weights; overkill for unweighted.