Back to Topics
Graph
A graph is a set of nodes (vertices) connected by edges. Edges can be directed or undirected, weighted or unweighted. Graphs model networks, dependencies, and spatial problems. DFS and BFS are the core traversal algorithms; topological sort and union-find are essential for directed and connectivity problems respectively.
Key Ideas
- Represented as adjacency list (space O(V+E)) or adjacency matrix (space O(V²))
- BFS finds shortest path in unweighted graphs; Dijkstra's for weighted
- DFS detects cycles, generates topological order, and finds connected components
- Topological sort: valid only for Directed Acyclic Graphs (DAGs) — used in dependency resolution
- Union-Find (Disjoint Set Union) tracks connected components in near-O(1) per operation
- Always track visited nodes to avoid infinite loops on cyclic graphs
Complexity
| Operation | Time | Space |
|---|---|---|
| BFS / DFS traversal | O(V + E) | O(V) |
| Topological sort (Kahn's) | O(V + E) | O(V) |
| Union-Find (path compression) | O(α(n)) ≈ O(1) | O(V) |
| Dijkstra's (min-heap) | O((V+E) log V) | O(V) |
Common Patterns
BFS for Shortest PathLevel-by-level exploration guarantees shortest hop count in unweighted graphs.
DFS for Cycle DetectionTrack recursion stack state (WHITE/GRAY/BLACK) to detect back edges.
Topological Sort (Kahn's)Repeatedly remove nodes with in-degree 0; remaining nodes form the cycle.
Union-FindEfficiently merge sets and query connectivity — ideal for Kruskal's MST and number-of-islands variants.
Code Example
Number of islands — DFS flood fillpython
def num_islands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited
dfs(r+1, c); dfs(r-1, c)
dfs(r, c+1); dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count💡
Convert a 2D grid problem to a graph problem: each cell is a node, each valid neighbour is an edge.