DFS Visualizer Online

Pseudocode

DFS is usually written recursively, but the iterative form makes the stack explicit and avoids blowing the call stack on deep graphs. Both produce the same discovery order.

DFS(graph, source):
    time = 0
    visit(source)

visit(u):
    visited.add(u)
    disc[u] = ++time          // discovery time
    for each neighbor v of u:
        if v not in visited:
            parent[v] = u
            visit(v)
    fin[u] = ++time           // finish time

The discovery and finish times are the real product of DFS. The interval [disc[u], fin[u]] of a descendant nests strictly inside its ancestor, and that nesting property is what topological sort, cycle detection, Tarjan strongly connected components, articulation points and bridges are all built on.

Worked example, step by step

Run DFS from A on the graph the visualizer loads by default, always taking neighbors in alphabetical order.

Example graph: Undirected edges A-B (2), A-C (3), B-C (1) and C-D (4). DFS ignores the weights.

1. Visit A. disc[A] = 1. The first unvisited neighbor is B, so recurse immediately rather than also looking at C.
2. Visit B. disc[B] = 2. Neighbors are A, which is the parent and is skipped, and C, unvisited. Recurse into C.
3. Visit C. disc[C] = 3. Neighbors are A, B and D. A is visited and is not the parent, so A-C is a back edge and proves a cycle exists. B is the parent. D is unvisited, so recurse into D.
4. Visit D. disc[D] = 4. Its only neighbor is C, the parent. Nothing left to do, so fin[D] = 5.
5. Unwind. Control returns to C, which is out of neighbors, so fin[C] = 6. Then B finishes at 7, and A, whose remaining neighbor C is now visited, finishes at 8.

The traversal order is A, B, C, D. BFS happens to visit these four nodes in the same order, but the trees differ: BFS builds a shallow tree with A to B, A to C and C to D, while DFS builds the single chain A to B to C to D. The back edge C to A identifies the cycle A-B-C-A, and the nested intervals A[1,8], B[2,7], C[3,6], D[4,5] show the recursion depth directly.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

Each vertex is visited exactly once because the visited check guards the recursive call, and each edge is examined once from each endpoint, giving 2E inspections in an undirected graph and E in a directed one. Space is the visited set plus the recursion stack, both O(V). The recursion depth is the length of the longest simple path, so on a path graph of a million nodes a recursive implementation will overflow the call stack in most languages and you need the explicit-stack form.

When to use Depth-First Search, and when not to

Choose DFS when the question is about structure. Choose BFS when the question is about distance.

Common pitfalls

• Stack overflow on deep graphs. Recursive DFS recurses once per vertex on a path. Around 10,000 to 100,000 nodes, depending on the language, the call stack dies. Convert to an explicit stack, or raise the recursion limit deliberately if the language allows it.
• Treating the parent edge as a back edge. In an undirected graph every edge appears from both ends, so the edge back to your parent always looks like a back edge. Skip the parent explicitly, and remember that with parallel edges you must skip it only once.
• Using the visited set for directed cycle detection. In a directed graph, meeting a visited node does not imply a cycle. It might be a cross edge into a finished subtree. You need three colours: unvisited, in the current recursion stack, and finished. Only an edge into the recursion stack closes a cycle.
• Assuming the traversal order is unique. DFS output depends on the neighbor iteration order. Two correct implementations can produce different valid orders, which is why tests should assert properties rather than an exact sequence.

Frequently asked questions

What is depth-first search used for?

DFS underlies topological sorting, cycle detection, strongly connected components, articulation points and bridges, and maze generation. In production it drives dependency resolution in build tools and package managers, deadlock detection, and backtracking solvers for puzzles and constraint problems.

What is the time complexity of DFS?

O(V + E) time and O(V) space with an adjacency list. Each vertex is visited once and each edge inspected once from each endpoint. The space is the visited set plus the recursion stack, whose depth equals the longest simple path in the graph.

Is DFS recursive or iterative?

Either. The recursive form is shorter and makes the discovery and finish times fall out naturally. The iterative form uses an explicit stack and is what you need for graphs deep enough to overflow the call stack, roughly tens of thousands of nodes in a chain.

How does DFS detect a cycle?

In an undirected graph, an edge to a visited node that is not the current node parent closes a cycle. In a directed graph you must track which nodes are on the current recursion stack, because only an edge back into the stack is a true back edge. An edge to a finished node is a cross or forward edge and proves nothing.

Why does DFS use less memory than BFS?

DFS stores only the current root-to-node path, so its memory is proportional to depth. BFS stores an entire frontier, which on a wide graph can be a large fraction of all vertices. On a deep narrow graph the comparison flips and BFS is the lighter option.