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.

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

python

▶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

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.

06

Complexity

Time

O(V + E)

Space

O(V)

Each vertex marked once; each edge inspected once.