0

Depth First Search

Medium

Follow one branch as deep as it goes, then backtrack. Each fresh launch from an unvisited node is one connected component.

recursionconnectivity
TimeO(V + E)
SpaceO(V) recursion depth
Inputedges like 0-1,1-2 | start node
0123456

Depth first: go as deep as possible before backing up.

components0
1 / 23
dfs(u):
visit(u)
for v in adj[u]:
if v not visited: dfs(v)
for each node: if not visited: dfs(node) // counts components
Why it matters

DFS answers connectivity, cycles and ordering. It does not give shortest paths.

Practise this
Number of IslandsMClone GraphMSurrounded RegionsMPacific Atlantic Water FlowM
Keyboard
space play← → stepr restartctrl K search

More in Graphs

Breadth First Search
O(V + E)
Dijkstra Shortest Path
O(E log V)
Topological Sort (Kahn)
O(V + E)
Union-Find (DSU)
Near O(1) amortised per operation
Kruskal Minimum Spanning Tree
O(E log E)
Flood Fill / Number of Islands
O(rows * cols)
Next visualiser
Dijkstra Shortest Path