DFS of Graph
DFS of Graph: return the depth-first traversal order of a graph given as an adjacency list.
- 1 <= V <= 10⁴
- 0 <= E <= 10⁵
- Graph is undirected and given as an adjacency list
- Start from vertex 0 and visit neighbours in list order
Intuition
DFS of graph returns the depth-first traversal order of a graph given as an adjacency list. Depth-first means committing to one path and following it as far as it goes before backing up and trying an alternative. On a tree that needs no bookkeeping at all, because there is exactly one path to each node. On a graph it does, and the reason is cycles: - Without a visited set, any cycle sends the traversal round forever. So a visited set is not an optimisation here, it is what makes the algorithm terminate. The detail that matters is when to mark. Mark a vertex the moment you arrive, before recursing into its neighbours. Marking on the way out instead lets a neighbour queue the same vertex again while its exploration is still in progress, which produces duplicates and, on a cycle, never terminates. A second point is easy to overlook: a graph may be disconnected. Starting a single DFS from vertex 0 only reaches its component, so the outer loop must launch a fresh traversal from every still-unvisited vertex. The recursive form uses the call stack; an explicit stack gives the same traversal shape. Note the orders differ slightly — pushing neighbours in reverse order makes the explicit version match the recursive one, which is worth knowing if a problem checks the exact sequence.
The base traversal every algorithm in graph theory is built on. Two details make it correct rather than merely plausible: mark a vertex on arrival (not on departure), and launch from every unvisited vertex so disconnected components aren't missed. Cycle detection, topological sort and connected components are all this loop with something extra bolted on.
Approach
Before reading on: price up what plain recursion costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(V + E) time and O(V) space.
Mark on arrival, not on exit
Set a vertex visited as soon as it is entered, before exploring neighbours. Marking later lets a neighbour re-enter a vertex still being explored, producing duplicates and never terminating on a cycle.
Record then recurse
Append the vertex to the output when it is first visited, then recurse into each unvisited neighbour. The output order is the discovery order, which is what depth-first traversal means.
Understand why the visited set is essential
On a tree there is one path to each node and no set is needed. On a graph a cycle loops forever without it — this is the structural difference between the two cases.
Restart at every unvisited vertex
A graph may have several components, and a single DFS only covers the one containing its start. Loop over all vertices and launch a fresh traversal from each unvisited one.
Know the explicit-stack version
Dfs of graph using stack gives the same traversal shape without recursion-depth risk. Push neighbours in reverse order if the exact sequence must match the recursive version.
Cost of the traversal
Every vertex is visited once and every edge examined once — twice in an undirected graph, once from each end — giving O(V + E) time and O(V) space for the visited array and the stack.
Solution & live demo
Common pitfalls
Marking visited after the recursive call
def dfs(v):
for u in adj[v]:
if not seen[u]: dfs(u)
seen[v] = Truedef dfs(v):
seen[v] = True
order.append(v)
for u in adj[v]:
if not seen[u]: dfs(u)On any cycle two vertices recurse into each other before either is marked, and the recursion never terminates. The mark must be set the moment you arrive, so it's visible to everything reachable from here.
Starting only from vertex 0
dfs(0) return order
for s in range(n):
if not seen[s]: dfs(s)A graph need not be connected, so vertices unreachable from 0 would never appear in the output. Every unvisited vertex needs its own launch.
Checking the visited flag only at the top of dfs
def dfs(v):
if seen[v]: return
seen[v] = True
for u in adj[v]: dfs(u)for u in adj[v]:
if not seen[u]: dfs(u)Both terminate, but the first pushes a stack frame for every edge — including all the ones that immediately return. Filtering before the call keeps the recursion depth proportional to the path, not the edge count.
Edge cases
Outer loop restarts DFS at every unvisited vertex.
The vertex is already marked when the loop edge is examined — skipped.
Visited and recorded with no recursion.