GeeksforGeeks Easy

DFS of Graph

Return the depth-first traversal order of a graph given as an adjacency list.

graphdfstraversal

02

Intuition

DFS commits to one path and follows it as far as it goes before backing up. The only bookkeeping needed is a visited set — without it any cycle sends the traversal round forever. Mark a vertex the moment you arrive, not when you leave, so a neighbour can never queue it a second time.

How to spot this pattern

The base traversal every graph algorithm 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.

03

Approach

1

Recurse, marking on arrival

dfs(v): mark v visited, record it, then recurse into every unvisited neighbour. Marking before recursing is what makes cycles safe — a neighbour that loops back finds v already marked and stops.

2

Handle disconnected graphs

A single dfs(0) only reaches vertices connected to 0. Loop over all vertices and start a fresh DFS from each unvisited one, so every component is covered.

3

Recursion or explicit stack

The call stack is doing the work of a stack; swapping in an explicit list gives the same order (push neighbours in reverse to match) and avoids stack-overflow on deep graphs.

04

Solution & live demo

▶1def dfs_of_graph(n, adj):
▶2    seen = [False] * n
▶3    order = []
▶4    def dfs(v):
▶5        seen[v] = True            # mark on arrival
▶6        order.append(v)
▶7        for u in adj[v]:
▶8            if not seen[u]:
▶9                dfs(u)
▶10            # else: already visited — skip
▶11    for s in range(n):            # every component
▶12        if not seen[s]:
▶13            dfs(s)
▶14    return order

05

Common pitfalls

Marking visited after the recursive call

✗ Wrong

def dfs(v):
    for u in adj[v]:
        if not seen[u]: dfs(u)
    seen[v] = True

✓ Right

def 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

✗ Wrong

dfs(0)
return order

✓ Right

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

✗ Wrong

def dfs(v):
    if seen[v]: return
    seen[v] = True
    for u in adj[v]: dfs(u)

✓ Right

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.

06

Edge cases

Disconnected graph

Outer loop restarts DFS at every unvisited vertex.

Self-loop

The vertex is already marked when the loop edge is examined — skipped.

Isolated vertex

Visited and recorded with no recursion.

07

Complexity

Time

O(V + E)

Space

O(V)

Each vertex marked once; each edge inspected once.