Algorithms · DFS

Depth-first search

Going deep before wide, recursion and the explicit stack, entry and exit times, cycle detection with three states, components and backtracking, and the stack overflow trap.

Updated 2026-09-21

On this page

If BFS is a ripple spreading outward, DFS is a person in a maze who keeps walking forward until they hit a dead end, then backs up to the last junction and tries the other way. It visits the same nodes and costs the same, but the order is completely different — and that order is what makes it good at a different set of problems.

The map

Read this first when short on time. Every branch is a section below.

Figure 1. The whole article on one page. Every branch is a section below; fold what you know, open what you do not.

The idea: go deep, then back up

Pick a neighbour and go. From there, pick a neighbour and go again. Keep going until there is nowhere new to move, then step back to the last place that still had an untried branch and continue from there.

This is the same graph as the BFS article, so the two orders can be compared directly.

Figure 2. DFS from A, taking neighbours in alphabetical order. It reaches H — three steps away — sixth, long before it visits D, which is one step away. Depth order and distance order have nothing to do with each other.

That last point is the one to hold on to: DFS gives you no distance information at all. It may reach a far node early and a near node late. If the question is "how far", you want BFS. If the question is "is there a path", "how many groups are there" or "try every possibility", DFS is usually simpler and lighter.

The algorithm

DFS is naturally recursive, because "explore this node, then fully explore each neighbour" is a description of itself.

def dfs(graph, node, seen):
    seen.add(node)                     # mark on the way in
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(graph, nxt, seen)      # fully finish nxt before trying the next one
    # arriving here means this node's whole subtree is done

The recursion is doing the bookkeeping for you: the call stack is the stack of nodes on the current path. When you need control over that — or when the depth would be too great — write it out with an explicit stack.

def dfs_iterative(graph, start):
    stack = [start]
    seen = set()
    while stack:
        node = stack.pop()             # pop the BACK: that is the only difference from BFS
        if node in seen:
            continue
        seen.add(node)
        for nxt in reversed(graph[node]):   # reversed, so neighbours come out in order
            if nxt not in seen:
                stack.append(nxt)

Tip

BFS and DFS are the same loop with one word changed: BFS takes from the front of the queue, DFS takes from the back of the stack. Everything else that differs between them — shortest paths, memory use, what they are good at — follows from that single choice.

Two differences from the recursive version are worth noting. Nodes can be pushed more than once, so the check happens on pop as well, and neighbours must be pushed in reverse order for the visit order to match the recursive one. Neither affects correctness, only the exact sequence.

Cost. Every node and edge is touched once, so O(V + E), the same as BFS. Memory is the big difference: BFS holds a whole ring, which on a wide graph can be enormous, while DFS holds only the current path.

The two moments: entry and exit

Here is the idea that turns DFS from a traversal into a tool. Every node has two interesting moments, not one: the moment you arrive, and the moment everything below it is finished.

def dfs(node):
    clock[0] += 1
    entry[node] = clock[0]             # pre-order: on the way IN
    for nxt in graph[node]:
        if nxt not in entry:
            dfs(nxt)
    clock[0] += 1
    exit[node] = clock[0]              # post-order: on the way OUT

For the graph above, the intervals look like this:

Node	A	B	E	C	F	H	G	D
Entry	1	2	3	4	5	6	7	8
Exit	16	15	14	13	12	11	10	9

The intervals nest: A's interval (1, 16) contains B's (2, 15), which contains E's (3, 14), and so on. That nesting is the whole structure, and it gives two facts you can rely on:

Ancestor test in constant time. Node u is an ancestor of v exactly when u's interval contains v's. No walking required.
Exit order reversed is a valid dependency order. A node finishes only after everything it can reach has finished, so reversing the finish order puts every node before everything it depends on — which is a topological sort.

Post-order — doing work on the way out — is also where results get combined, because by then every child has already returned its answer. Computing the size of each subtree, the height of a tree, or whether a subtree contains something all happen naturally on the way out.

Finding cycles

The classic use of DFS, and the one where a small mistake gives a wrong answer that looks right.

The naive approach — "if I reach a node I have already seen, there is a cycle" — is wrong. Seeing a node again only means there are two routes to it, which in a directed graph is perfectly normal. What matters is whether the node you reached is still on the path you are currently walking.

So a node has three states, not two:

Figure 3. Why two states are not enough. An edge back to a node that is merely finished is a shortcut through the graph; an edge back to one that is still in progress closes a loop.

UNSEEN, IN_PROGRESS, DONE = 0, 1, 2

def has_cycle(graph):
    state = {node: UNSEEN for node in graph}

    def visit(node):
        state[node] = IN_PROGRESS
        for nxt in graph[node]:
            if state[nxt] == IN_PROGRESS:      # back to the current path
                return True
            if state[nxt] == UNSEEN and visit(nxt):
                return True
        state[node] = DONE                     # only now is it safe
        return False

    return any(visit(n) for n in graph if state[n] == UNSEEN)

Undirected graphs are different. There, every edge goes both ways, so the edge you just came along always leads back to an in-progress node — your parent. That is not a cycle. The rule becomes: a cycle exists if you reach a seen node that is not the node you came from.

Watch out

The parent check breaks if the graph can have two separate edges between the same pair of nodes, because the second one genuinely is a cycle but looks like the parent edge. If parallel edges are possible, track the edge you arrived on rather than the node.

What DFS is good for

Four families, all of which lean on "finish this whole branch before moving on".

Connected components. Loop over every node; when you find one that has not been visited, run a DFS from it and label everything it reaches. The number of times you had to start a new DFS is the number of components. This is the standard way to count islands in a grid, group related records, or find isolated parts of a network.

Flood fill. The same thing on a grid: from one cell, spread to every connected cell matching some condition. Paint-bucket tools, region selection and "how big is this blob" are all this. BFS works equally well here — the choice is purely about recursion depth.

Backtracking. This is DFS over a tree of possibilities that you build as you go rather than a graph that already exists. The shape is always the same three steps:

def solve(state):
    if complete(state):
        record(state)
        return
    for move in options(state):
        apply(state, move)        # choose
        solve(state)              # recurse
        undo(state, move)         # un-choose: the part people forget

Permutations, sudoku, n-queens, word searches and puzzle solvers are all this loop with different options and complete. The undo step is what makes it a search rather than a one-way walk, and forgetting it is the classic bug.

Structure. The deeper algorithms — bridges and articulation points (which edges or nodes would disconnect the graph if removed), and strongly connected components — are all built on entry and exit times. They are worth knowing exist, because when a problem asks "what single failure would split this network", that is the family to reach for.

The stack trap

One practical problem bites often enough to deserve its own section: recursion depth is the length of the longest path, and many languages limit that to a few thousand frames.

It is easy to assume this is theoretical. It is not. A grid of a million open cells with no walls is not a wide graph to DFS — it is one enormous winding path, and a recursive DFS will go a million frames deep and crash. A linked list or a degenerate tree does the same.

Option	Cost
Raise the recursion limit	One line, but the real limit is the operating system's stack size, so it can crash rather than raise a clean error
Write the explicit stack version	Uglier and harder to get post-order right, but bounded only by heap memory
Use BFS instead	Free when the traversal order does not matter, which for components and flood fill it does not

For flood fill and component counting specifically, BFS is the safer default for exactly this reason — the two produce identical answers, and only one of them can overflow the stack.

Recap

DFS follows one path as far as it goes, then backs up to the last junction with an untried branch. BFS finishes a ring; DFS finishes a path.
It is the same loop as BFS with one word changed: take from the back of a stack instead of the front of a queue.
DFS gives no distance information — it can reach a far node early and a near one late. For shortest paths, use BFS.
Recursion is the natural form, because the call stack is the stack of nodes on the current path.
Time is O(V + E), the same as BFS. Memory is one path rather than one ring, which is DFS's real advantage.
Every node has two moments: entry on the way in, exit when its whole subtree is finished. Almost every DFS technique uses one of them.
Entry and exit intervals nest, so one node is an ancestor of another exactly when its interval contains the other's.
Reversing the exit order gives a topological order, because a node finishes only after everything it can reach.
Post-order is where child results get combined — subtree sizes, heights, "does this subtree contain X".
Cycle detection needs three states, not two: an edge to a finished node is a harmless shortcut, an edge to an in-progress node is a cycle.
In an undirected graph the rule changes to "a seen node that is not the parent", and parallel edges break that unless you track the edge you arrived on.
DFS is the tool for components, flood fill, backtracking (choose, recurse, un-choose) and the structural algorithms built on entry and exit times.
Recursion depth equals the longest path, so a large grid or a long chain overflows the stack. Use the explicit stack version, or BFS, when depth could be large.

Questions

Try answering each one out loud before opening it. Lead with the one-line answer, then the reasoning, then one detail that shows depth.

What is the difference between DFS and BFS in one sentence?

BFS takes the next node from the front of a queue and so explores in rings of increasing distance, while DFS takes it from the back of a stack and so follows one path to its end before trying alternatives.

Both visit every node and edge once, so both are O(V + E).
Only BFS gives shortest paths, because only BFS visits in distance order.
DFS holds one path in memory; BFS holds an entire level, which can be far larger.

The implementations differ by a single line, which is a good way to remember that everything else is a consequence of the order.

Why can't DFS be used to find the shortest path?

Because it visits in depth order, not distance order — it can reach a node three steps away long before one that is a single step away, and the first path it finds to a node is simply the first one it stumbled into.

In the article's example DFS reaches H, three steps out, before D, which is adjacent to the start.
You could find every path and keep the shortest, but that is exponential work for something BFS does in one pass.
On a weighted graph neither works, and you need Dijkstra.

DFS does answer "is there any path", which is often the actual question.

Write DFS without recursion. What changes?

Use an explicit stack: push the start, then repeatedly pop a node, skip it if already seen, mark it, and push its unseen neighbours. Two things change from the recursive version.

Nodes can be pushed more than once before being popped, so the visited check must happen on pop as well.
Neighbours must be pushed in reverse order for the visit sequence to match the recursive version.
Post-order work is harder, since you no longer get the "returning from a call" moment for free.

The usual trick for post-order iteratively is to push each node twice, with a marker, and do the exit work when you pop the marked copy.

What are entry and exit times, and what are they for?

Entry is a counter value recorded when DFS arrives at a node, exit when its entire subtree is finished; the pair forms an interval, and intervals nest along the DFS tree.

Nesting means one node is an ancestor of another exactly when its interval contains the other's — a constant-time test.
Reversing the exit order gives a topological order.
Bridges, articulation points and strongly connected components are all built from these numbers.

Recognising that DFS gives two moments per node rather than one is what unlocks most of the non-obvious applications.

Why does cycle detection need three states rather than a visited set?

Because reaching an already-seen node only means there were two routes to it, which is normal in a directed graph; a cycle exists only if the node you reached is still on the path you are currently walking.

"In progress" marks nodes between the root and the current position; "finished" marks nodes whose subtree is fully explored.
An edge to a finished node is a shortcut and is harmless.
Marking a node finished too early, before its children return, breaks the whole test.

Using only a visited set reports cycles in perfectly acyclic graphs, and the bug survives small test cases easily.

How does cycle detection differ in an undirected graph?

Every edge goes both ways, so the edge you arrived on always leads back to an in-progress node — your parent — which is not a cycle. The rule becomes: a cycle exists if you reach a seen node that is not your parent.

Three states are unnecessary here; a visited set plus the parent is enough.
Parallel edges break the parent check, because the second edge is a real cycle that looks like the one you came on.
The fix is to track the edge identifier you arrived on rather than the node.

Union-find is the other standard answer for undirected cycle detection, and it handles edges arriving one at a time.

How do you count connected components?

Loop over every node; whenever you find one that has not been visited, start a DFS from it and label everything it reaches, then increment a counter. The counter ends as the number of components.

The total work is still O(V + E), because each node and edge is handled once across all the searches.
The same loop labels each node with its component id, which is often more useful than the count.
BFS works identically here, and is safer when components can be very large.

Counting islands in a grid is exactly this, with the grid's implicit four-neighbour adjacency.

What is the shape of a backtracking algorithm?

Choose, recurse, un-choose: apply a move to the state, recurse to explore everything reachable from there, then undo the move before trying the next option.

It is DFS over a tree of possibilities that is generated as you go rather than stored.
Forgetting the undo is the classic bug, and it produces answers polluted by earlier branches.
Pruning — abandoning a branch as soon as it cannot lead to a solution — is what makes it practical.

Permutations, sudoku and n-queens are the same loop with different move generators and completion tests.

Why does post-order matter?

Because by the time DFS returns from a node, every child has already finished and returned its result — so post-order is the natural place to combine answers from below.

Subtree sizes, tree heights and "does this subtree contain X" are all computed on the way out.
Pre-order is for work that only needs information from above, such as passing down a depth or a path.
Reversed post-order is a topological order, which is the same fact applied to a directed graph.

Asking "do I need information from above or from below" is usually enough to decide which of the two moments to use.

When does recursive DFS crash, and what do you do about it?

When the longest path exceeds the recursion limit — which happens sooner than people expect, because a large open grid is effectively one long winding path rather than a wide shallow graph.

A million-cell grid can drive a million stack frames.
Raising the limit helps only until the operating system's stack runs out, which crashes rather than raising a clean error.
The explicit stack version is bounded by heap memory instead, and BFS avoids the problem entirely.

For flood fill and component counting, where order does not matter, BFS is the safer default for exactly this reason.

When would you prefer DFS over BFS?

When you do not need distances and memory matters, or when the problem is naturally recursive: components, flood fill, cycle detection, topological sorting, backtracking, and anything needing entry and exit times.

DFS holds one path; BFS holds a whole level, which on a wide graph can be most of the graph.
Recursive DFS is often a third the code of the equivalent BFS.
BFS wins when the answer is likely close to the start, since it will find it without exploring deep dead ends.

If both work, pick by which failure mode you would rather have: BFS runs out of memory on wide graphs, DFS runs out of stack on deep ones.

How would you detect whether a graph is bipartite?

Two-colour it during a traversal: give the start one colour and every neighbour the opposite, and report failure if you ever find an edge joining two nodes of the same colour.

Either DFS or BFS works, since the colouring depends only on parity of depth in the traversal tree.
A conflict means an odd-length cycle, which is exactly what makes a graph non-bipartite.
Every component must be checked separately, since a disconnected graph can have one bad piece.

It is a good example of a problem where the traversal itself is trivial and all the content is in what you record while traversing.