vizlearn

Home / Graph Algorithms

DFS Explorer

Algorithms & Data StructuresBy Ashish JangraUpdated 26 October 2026

Visualize recursive path exploration using the LIFO Stack strategy.

Graph Config

Structure Type

Search Speed

Search Statistics

Visited Nodes 0

Maximum Depth 0

Exploration Map

Ready

Click a node to set as start point • Default is 'A'

LIFO Stack

Stack is empty

Traversal Order

DFS prioritizes depth by exploring one branch as far as possible before backtracking to the nearest unexplored neighbor.

Overview

Mark the start visited. Choose an unvisited neighbour and continue; when the current node has no unvisited neighbours, return to the previous node. The order depends on the graph’s neighbour ordering, but every reachable node is visited once when a visited set is used.

Follow a path, then backtrack

Choose Structure Type in the visualizer, then press Start Search and Step to see one path grow and retreat. Auto completes the traversal; Reset State starts again. A different neighbour order can produce a different valid DFS order.

A graph implementation

def dfs(graph, start):
    seen = set()
    order = []

    def visit(node):
        seen.add(node)
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                visit(neighbour)

    visit(start)
    return order

The recursive calls form an implicit stack. A node is marked when first reached, which prevents a cycle from repeating the traversal.

What DFS is useful for

DFS can explore connected components, detect cycles, produce a topological order in a directed acyclic graph, and support maze or state-space search. It does not guarantee the shortest path. For shortest paths by edge count in an unweighted graph, use breadth-first search.

With an adjacency-list graph, DFS takes O(V + E) time and O(V) extra space for visited nodes and the call stack. Recursive DFS is concise, but a very deep graph can exceed the language’s call-stack limit; an explicit stack avoids that recursion limit.

Common mistakes with Depth First Search

Skipping the visited set: cycles can send the search around forever.
Marking only after exploring neighbours: a node may be pushed repeatedly; mark it when discovered.
Assuming one fixed traversal order: it depends on the order in which neighbours are listed.
Using DFS for shortest paths: depth-first order does not minimize distance.

Sources and next steps

Princeton Algorithms: Depth-first search explains graph traversal and DFS applications.
Continue with breadth-first search, cycle detection, and topological sort.

Run it in Python

The same traversal written twice — once recursively and once with an explicit stack — so you can see that the call stack and the stack you push to by hand are the same object.

dfs.pyPython 3

# Depth-first search: follow one path as far as it goes, then back up.

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": ["G"],
    "G": [],
}

# --- 1. recursive: the call stack does the remembering -------------------
def dfs_recursive(node, visited=None, depth=0):
    if visited is None:
        visited = set()
    visited.add(node)
    print(f"{'  ' * depth}enter {node}")
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs_recursive(neighbour, visited, depth + 1)
    print(f"{'  ' * depth}leave {node}")
    return visited


print("recursive:")
dfs_recursive("A")

# --- 2. iterative: the same stack, made explicit ------------------------
def dfs_iterative(start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()               # pop = LIFO = depth-first
        if node in visited:
            continue                     # a node can be stacked twice
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):   # reversed: match recursion
            if neighbour not in visited:
                stack.append(neighbour)
    return order


print()
print("iterative:", " -> ".join(dfs_iterative("A")))

# Cycle safety: the visited set is the only thing preventing an infinite loop.
graph["G"] = ["A"]
print()
print("with a G -> A edge added back:")
print("iterative:", " -> ".join(dfs_iterative("A")))

Output

How the code works

visited.add(node) before recursingMarking on entry is what makes the traversal terminate. A graph is not a tree — without this, the G → A edge added at the end sends the function round forever.
print enter / print leaveThe pair brackets each call, so the output is literally the shape of the call stack over time. Post-order work — topological sort, subtree sizes — belongs on the “leave” line.
node = stack.pop()The last node pushed is the next explored, which is what “depth first” means mechanically. BFS is the same loop with a queue.
if node in visited: continueThe iterative version needs a second check because a node can be pushed by several neighbours before it is popped. Skipping this does not loop forever, but it does visit nodes twice.
for neighbour in reversed(graph[node]):A stack reverses order, so pushing the neighbour list backwards makes the iterative version explore in the same order as the recursive one. Without it both are valid DFS, just different DFS.

Change one thing

Delete visited.add(node) from the recursive version and run it with the G → A edge in place. The RecursionError is the base case you removed.
Move the leave print above the loop. The output is no longer nested, which shows what pre-order and post-order actually mean.
Chain a thousand nodes together and call the recursive version. It hits Python's recursion limit; the iterative one does not care.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Predict, then reveal

About to run: set Search Speed to its minimum (1). Before it does — what happens to the readout?

Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.

Check yourself

0 of 3

Answer without scrolling back up.

Without the visited set, DFS on a graph containing a cycle:
Why does the iterative version also check 'if node in visited' after popping?
Work that belongs on the "leave" line - after the recursive calls return - includes:

Cheat sheet

Depth First Search

Follow depth-first search as far down one branch as it goes, then watch it backtrack and take the next unexplored edge.

ALGORITHMS · vizlearn.in/dsa/depth_first_search.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

About VizLearn GitHub LinkedIn Contact