Graphs, BFS & DFS

DSA · Intermediate

Definition

A graph is a set of nodes connected by edges. BFS explores level by level; DFS goes deep before backtracking.

Maps, social networks, dependencies and networks are all graphs.

Diagram

Flowchart

Example: BFS traversal

from collections import deque
g = {'A':['B','C'],'B':['D'],'C':['D'],'D':[]}
seen, q, order = {'A'}, deque(['A']), []
while q:
    n = q.popleft(); order.append(n)
    for m in g[n]:
        if m not in seen:
            seen.add(m); q.append(m)
print(order)

Output: ['A', 'B', 'C', 'D']

Complexity

O(V + E)

Key points

BFS gives shortest path in unweighted graphs
DFS detects cycles and does topological sort
Dijkstra for weighted shortest paths

Interview questions

Count islands in a grid?

Run DFS/BFS from each unvisited land cell and count starts.

What is topological sort?

Ordering of a DAG where each edge goes from earlier to later.