patternDSA/Graphs
Core Pattern → Pattern 17

Graphs

Every graph problem reduces to DFS (connectivity, cycles) or BFS (shortest paths). The visited set is the only structural difference from tree traversal — and it's mandatory.

Frequency:★★★★★
·~30 min·Intermediate·5 problems
The Core Shock

Tree traversal: no visited set needed. Graph traversal without one: infinite loop.

Graph DFS/BFS, no visited set
TLE / ∞ loop
Cycles loop forever. DAGs get O(2^n) revisits.
Graph DFS/BFS + visited set
O(V + E)
Each node and edge processed exactly once.

Trees are acyclic — you can never revisit a node. Graphs can have cycles and shared paths. The visited set is the only structural difference between tree and graph traversal. It converts O(2^n) or infinite loops into O(V+E).

Graph Representations

Build the right structure first.

Adjacency ListMost problems
graph = {}
for u, v in edges:
    graph.setdefault(u,[]).append(v)
    graph.setdefault(v,[]).append(u) # undirected
# O(V+E) space. Fast neighbor iteration.
Adjacency MatrixDense / edge lookup
mat = [[0]*n for _ in range(n)]
for u, v in edges:
    mat[u][v] = 1  # mat[v][u]=1 undirected
# O(V²) space. O(1) edge existence check.

DFS vs BFS

Two seconds to decide.

DFS — connectivity
Path exists between two nodes
Count connected components
Cycle detection (3-color)
Find eventual safe states
Topological sort (post-order)
Explore entire component
BFS — shortest paths
Shortest path in unweighted graph
Minimum hops/steps/transfers
Level-order by distance
Multi-source BFS
Nearest node satisfying condition
Flood fill / island expansion

Recognition Cheat Sheet

Signal words → algorithm.

"exists", "can reach", "connected"DFS + visited
"shortest", "minimum hops", "fewest"BFS + visited
"components", "groups", "provinces"DFS outer loop
"safe", "cycle detection", "terminal"3-color DFS
"must start from", "in-degree 0"In-degree reasoning
"route", "transfer", "bus"BFS on routes