DFS Visualizer — Depth-First Search

How it works

1. Start a clock at time = 0 and call visit(s) on the start node.
2. In visit(u), set disc[u] = ++time and push u onto the stack of nodes on the current path.
3. For each neighbour v of u: if v is unvisited, call visit(v) — the edge u–v becomes a tree edge.
4. If v is still on the stack, u–v is a back edge and closes a cycle; if v is already finished, skip it.
5. When every neighbour is handled, set fin[u] = ++time and pop u: DFS backtracks to the node that called it.
6. To cover a disconnected graph, start a new visit from every node that is still unvisited.

How DFS backtracks

Picture exploring a maze while unrolling a ball of thread: walk down a corridor until you hit a dead end or a room you have already seen, then wind the thread back to the last junction with an unexplored door. The thread is the stack — in a recursive implementation, the call stack itself.

Only the current path needs to be remembered, so DFS uses O(depth) extra space, which is O(V) in the worst case (a graph shaped like a long path). That depth is also its main practical risk: Python's default recursion limit is 1000, so large graphs need sys.setrecursionlimit or an explicit stack. An iterative DFS that matches the recursive order pushes neighbours in reverse and marks a node visited when it is popped, not when it is pushed.

Worked example: discovery and finish times

The page opens on the same 7-node undirected graph as the BFS page (edges A–B, A–C, B–C, B–D, B–E, C–D, C–F, D–E, D–F, E–G, F–G), with neighbours taken in alphabetical order. From A:

• A is discovered at time 1, B at 2, C at 3. C's neighbour A is still on the stack, so C–A is a back edge — it closes the triangle A–B–C.
• C goes on to D (4). D sees B on the stack (back edge D–B) and moves to E (5); E sees B (back edge E–B) and moves to G (6), and G moves to F (7).
• F's other neighbours C and D are both on the stack (back edges F–C and F–D). F has nowhere new to go, so it finishes at 8, then G at 9, E 10, D 11, C 12, B 13 and A 14.

The visit order is A, B, C, D, E, G, F, and the DFS tree is a single path six edges deep — compare that with the three levels of the BFS tree on the same graph. There are 5 back edges, exactly E − (V − 1) = 11 − 6: in a connected undirected graph, every edge that is not in the DFS tree is a back edge and closes its own cycle.

The times obey the parenthesis property: two intervals [disc, fin] are either nested or disjoint, and u is an ancestor of v exactly when u's interval contains v's — B's [2, 13] contains E's [5, 10].

Edge types and cycle detection

• Tree edge: leads to an unvisited node; together these form the DFS tree (or forest).
• Back edge: leads to an ancestor that is still on the stack. It is the only edge type that proves a cycle.
• Forward and cross edges (directed graphs only): lead to a node that has already finished — a descendant or a node in another branch. Neither closes a cycle.

So a directed graph has a cycle exactly when DFS finds a back edge, which is why directed cycle detection tracks three states (unvisited, on the stack, finished) rather than a single visited flag. In an undirected graph every edge to an already visited node is a back edge, except the edge you just arrived on — skip the parent, or every edge will look like a cycle. Finish times matter too: reversed finish order of a DAG is a topological order, and Kosaraju's algorithm uses finish order to find strongly connected components.

Common mistakes

• No parent check in undirected cycle detection: the edge back to the parent is reported as a two-node cycle.
• A single visited flag for directed cycle detection: reaching a finished node through a cross edge is not a cycle; you need the on-stack ("grey") state.
• Expecting shortest paths: DFS finds a path, usually not the shortest one. Use BFS or Dijkstra for that.
• Starting from one node only on a disconnected graph, so whole components are never visited.
• Stack overflow on deep graphs — switch to an explicit stack.

Where DFS is used

DFS is the workhorse behind many graph algorithms: cycle detection, topological sorting, strongly connected components (Kosaraju and Tarjan), bridges and articulation points (via low-link values), connected components and flood fill, and maze generation and solving. Preorder, inorder and postorder traversals of a binary tree are DFS on a tree, and backtracking search — N-queens, Sudoku, generating permutations — is DFS over an implicit tree of choices.

Typical interview problems: number of islands, course schedule (is there a cycle?), clone a graph, all paths from source to target, and detecting a cycle in a directed graph.

Time and space complexity

Depth-First Search in Python

def dfs(graph, s):
    """graph: {node: [neighbours]}. Returns discovery / finish times and back edges.
    (Undirected graph: the edge back to u's parent also shows up as a back edge.)"""
    disc, fin = {}, {}
    on_stack = set()                     # nodes on the current call stack
    back_edges = []
    time = 0

    def visit(u):
        nonlocal time
        time += 1
        disc[u] = time
        on_stack.add(u)                  # push u
        for v in graph[u]:
            if v not in disc:            # v is unvisited
                visit(v)                 # tree edge
            elif v in on_stack:          # v is an ancestor of u
                back_edges.append((u, v))  # back edge: a cycle
            # else: v is finished - skip it
        time += 1
        fin[u] = time
        on_stack.remove(u)               # pop u

    visit(s)
    return disc, fin, back_edges

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• BFS Visualizer — Breadth-First SearchBreadth-first search explores a graph level by level with a queue and finds fewest-edge paths. Watch BFS run step by step, with code and O(V + E) analysis.
• Topological Sort VisualizerA topological sort orders the nodes of a DAG so every edge points forward. Watch Kahn's algorithm step by step, see why cycles block it, and get the code.
• Strongly Connected Components VisualizerStrongly connected components are groups of nodes in a directed graph that can all reach each other. Watch Kosaraju's algorithm find them step by step.
• Stack VisualizerInteractive stack visualizer: watch push, pop and peek move the top pointer of an array stack, see overflow and underflow happen, and learn why each is O(1).
• Tree Traversal Visualizer — Inorder, Preorder, Postorder, Level OrderVisualize inorder, preorder, postorder and level-order tree traversal on one tree: the visit order, the call stack or queue, the code, and when to use each.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.