Visualize recursive path exploration using the LIFO Stack strategy.
Overview
Go deep first, backtrack second
Start at a node and mark it visited. Pick any unvisited neighbour and move there. Repeat. When a node has no unvisited neighbours left, back up to the previous node and try its next neighbour. The search finishes when it has backed all the way out of the start node.
The behaviour comes entirely from using a stack: the most recently discovered node is the next one explored, so the frontier keeps extending forwards rather than fanning out. Recursion gives you that stack for free, which is why DFS is usually four lines of code.
Graph Config
Search Speed
Search Statistics
Visited Nodes0
Maximum Depth0
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.
Depth First Search: A Practical Guide
Follow one path as far as it goes, then back up and take the next. Depth-first search is the traversal that answers reachability and structure questions - but it will not give you a shortest path.
Trace it on a small graph
Take the graph with edges A–B, A–C, B–D, C–D, D–E, starting at A and preferring alphabetical order:
visit A → visit B → visit D → visit E
E has no unvisited neighbours → back up to D
D’s neighbour C is unvisited → visit C
order: A, B, D, E, C
Notice that C is adjacent to A and yet is visited last. DFS has no sense of distance from the start — it went three hops deep before coming back for a direct neighbour. That single observation is why DFS cannot be used for shortest paths.
Complexity, and the visited set
DFS is O(V + E): every vertex is pushed and popped once, and every edge is examined once from each endpoint. Space is O(V) for the visited set plus O(h) for the stack, where h is the length of the longest path explored — which in the worst case is V.
The visited set is not an optimisation, it is a correctness requirement. Without it, any cycle sends the search around forever, and even in an acyclic graph a diamond shape causes exponential re-exploration of shared subgraphs.
Following one path to the end
Depth-first search goes as deep as it can along one branch before backtracking to try another.
The mechanism is a stack — explicitly, or implicitly through recursion. Recursion is the natural expression:
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
for nbr in graph[node]:
if nbr not in visited:
dfs(graph, nbr, visited)
return visited
The iterative form makes the stack explicit, and it is what you need when the graph is deep enough to exceed Python's recursion limit of about 1,000 frames:
def dfs_iter(graph, start):
visited, stack = set(), [start]
while stack:
node = stack.pop() # from the END - that is what makes it DFS
if node in visited:
continue
visited.add(node)
stack.extend(graph[node])
return visited
The single difference from BFS is stack.pop() against queue.popleft(). Last-in-first-out gives depth-first; first-in-first-out gives breadth-first. Everything else is identical.
Three orders for trees
On a tree, when you process a node relative to its children gives three traversals, and each has a purpose:
Order
Sequence
Use
Pre-order
Node, left, right
Copying a tree, serialising, prefix expressions
In-order
Left, node, right
Sorted order in a binary search tree
Post-order
Left, right, node
Deleting a tree, evaluating expressions, computing sizes
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.value) # between the two recursions
inorder(node.right, out)
The in-order row is the important one: an in-order traversal of a binary search tree visits values in ascending order, which is why BSTs support sorted iteration and hash tables do not.
Post-order is the one to reach for when a node's result depends on its children — computing subtree sizes, heights, or deleting nodes safely.
What DFS is naturally good at
Connectivity. Run DFS from a node; whatever it reaches is that node's connected component.
Cycle detection. A cycle exists if DFS encounters a node currently on the recursion stack. Note the distinction: on the stack, not merely visited — a visited node not on the current path is a cross edge, not a cycle.
Topological sorting. The reverse of the post-order finishing sequence is a valid topological order for a directed acyclic graph.
Path finding and backtracking. Exploring a decision tree — sudoku, n-queens, permutations — is DFS with undo.
Strongly connected components. Tarjan's and Kosaraju's algorithms are both built on DFS.
BFS can do connectivity too. What BFS cannot easily do is anything requiring knowledge of the current path, which is exactly what the recursion stack gives DFS for free.
The three orders, and what each one is for
DFS is usually shown as one traversal, but the position of a single line -- where you do the work relative to the recursive calls -- gives three different orders with three different uses. On a binary tree the difference is easy to miss and easy to demonstrate.
example_01.pyPython
TREE = {
"F": ("B", "G"),
"B": ("A", "D"),
"A": (None, None),
"D": ("C", "E"),
"C": (None, None),
"E": (None, None),
"G": (None, "I"),
"I": ("H", None),
"H": (None, None),
}
def walk(node, order, out):
if node is None:
return
left, right = TREE[node]
if order == "pre":
out.append(node)
walk(left, order, out)
if order == "in":
out.append(node)
walk(right, order, out)
if order == "post":
out.append(node)
for order, use in (("pre", "copy or serialise the tree"),
("in", "read a BST in sorted order"),
("post", "free or evaluate children first")):
out = []
walk("F", order, out)
print("%-5s %s <- %s" % (order + ":", " ".join(out), use))
# One line moved, three orders. The IN-order line is the one worth
# noticing: this tree is a binary search tree, and reading it in-order
# produces A B C D E F G H I -- sorted, for free, with no comparisons at
# all beyond the ones already spent building it.
#
# POST-order is the one you need when a node's work depends on its
# children being done first. Computing the height of the tree is the
# canonical case, and it cannot be done pre-order:
def height(node):
if node is None:
return 0
left, right = TREE[node]
return 1 + max(height(left), height(right))
print()
print("height of the tree:", height("F"))
# Now the same algorithm on a general graph, where the extra requirement
# is a visited set -- without it, a cycle makes DFS run forever.
GRAPH = {1: [2, 3], 2: [4], 3: [4], 4: [1]} # note 4 -> 1 closes a cycle
def dfs(graph, start, seen=None, out=None):
seen = set() if seen is None else seen
out = [] if out is None else out
if start in seen:
return out
seen.add(start)
out.append(start)
for nxt in graph[start]:
dfs(graph, nxt, seen, out)
return out
print("graph DFS from 1:", dfs(GRAPH, 1))
# Four nodes, four edges, one cycle, and it terminates -- because the
# second time anything reaches node 1 the visited set stops it. Delete
# that check and this is an infinite recursion, which is the single most
# common DFS bug.
#
# The visited set is also what makes the complexity O(V + E) rather than
# something worse: every node is expanded once, and every edge is examined
# once from each end it is stored under.
print()
print("nodes = %d, edges = %d, so O(V + E) = %d units of work"
% (len(GRAPH), sum(len(v) for v in GRAPH.values()),
len(GRAPH) + sum(len(v) for v in GRAPH.values())))
Output
Things to try
Watch it commit to one branch. Press Start Search and then Step repeatedly. The frontier is always a single path running away from the start — nothing fans out sideways.
Catch a backtrack. Keep stepping until the search hits a node with no unvisited neighbours. The highlight jumps backwards to the previous node. That jump is the stack popping, and it is the only moment DFS moves toward the start.
Slow it down. Set Search Speed to 1 and press Auto. At low speed the dive-and-retreat rhythm is obvious: long runs forward punctuated by sharp jumps back.
Change the shape. Switch Structure Type and press Reset State, then run again. On a wide, shallow structure DFS still refuses to explore breadthwise — it takes the first branch to its end regardless.
What DFS is good for
DFS answers questions about structure and connectivity rather than distance:
Cycle detection. If the search reaches a node already on the current recursion stack, there is a cycle. (Already visited is not enough — it must be on the current path.)
Topological sort. Push each node onto an output stack as its recursion finishes; the reversed finish order is a valid topological ordering of a DAG.
Connected components. Run DFS from each unvisited node; each run marks exactly one component.
Strongly connected components via Tarjan’s or Kosaraju’s algorithm, both built directly on DFS finish times.
Maze and puzzle solving where a solution is wanted rather than the shortest one.
Common mistakes
Using it for shortest paths. DFS finds a path, essentially never the shortest. Unweighted shortest paths need BFS; weighted need Dijkstra.
Stack overflow on deep graphs. Recursive DFS on a graph with a path of 100,000 nodes exhausts the call stack in most languages. Convert to an explicit stack when depth may be large.
Marking visited at the wrong moment. Mark a node when you push it, not when you pop it. Marking on pop lets the same node enter the stack many times before it is first processed.
Confusing “visited” with “on the current path” for cycle detection. Distinguishing the two — often white / grey / black colouring — is what makes cycle detection correct on a directed graph.
In one line
Depth-first search uses a stack to follow one path to exhaustion before backtracking, running in O(V + E) with O(h) stack space. It answers structural questions — cycles, components, topological order — extremely cheaply, and it is the wrong tool for anything involving distance, because it will happily visit a direct neighbour of the start last.
Cycle detection, done correctly
In a directed graph, three states are needed rather than two:
WHITE, GREY, BLACK = 0, 1, 2 # unvisited, on the stack, finished
def has_cycle(graph):
colour = {n: WHITE for n in graph}
def visit(n):
colour[n] = GREY
for m in graph[n]:
if colour[m] == GREY: # back edge to the current path
return True
if colour[m] == WHITE and visit(m):
return True
colour[n] = BLACK
return False
return any(visit(n) for n in graph if colour[n] == WHITE)
The grey state is the whole point. Meeting a grey node means an edge back to something on the current path — a cycle. Meeting a black node means an already-finished subtree, which is not a cycle. Using a single visited set conflates the two and reports cycles that do not exist.
In an undirected graph it is simpler: a cycle exists if DFS reaches an already-visited node that is not the immediate parent.
Recursion depth, the practical limit
Python's default recursion limit is about 1,000 frames. A graph that is a long chain — a linked list, a path graph, a deep tree — will exceed it.
Three responses:
Convert to the iterative form with an explicit stack. Always available, and it is what production code should use for arbitrary input.
Raise the limit with sys.setrecursionlimit. Works up to the actual C stack size, and a segmentation fault is the failure mode rather than a clean exception.
Increase the thread stack size and run the search in a thread. Occasionally used, and awkward.
The iterative version has one subtlety: to replicate post-order (needed for topological sort), the node must be pushed back with a marker after its children, or visited in two phases. That is why recursive DFS is preferred where depth allows — the ordering comes free.
Complexity and where each is cheaper
Time: O(V + E) for both DFS and BFS — each node and edge examined once.
Space: DFS is O(depth), BFS is O(width). That difference decides which is usable on a large graph.
Graph shape
Cheaper
Deep and narrow (a long chain)
BFS — small frontier
Wide and shallow (a social graph)
DFS — short path
Balanced tree
Similar
Grid
Similar; BFS if you need distance
Questions people ask
Recursive or iterative? Recursive is clearer and hits Python's stack limit on deep graphs. Use iterative for arbitrary input.
Does DFS find the shortest path? No. It finds a path, which may be much longer than the shortest. Use BFS on unweighted graphs.
Why three colours for cycle detection? To distinguish an edge back to the current path (a cycle) from an edge into a finished subtree (not a cycle).
Can DFS handle disconnected graphs? Run it from every unvisited node; each run finds one component.
What is the difference from backtracking? Backtracking is DFS over a state space with explicit undo, and usually with pruning of branches that cannot succeed.
How do I get a topological order? Reverse the post-order finishing sequence, and check for cycles — a cyclic graph has no topological order.
Recap in one screen
A stack — explicit or via recursion — makes exploration go deep before wide.
Pre-, in- and post-order differ only in when the node is processed; in-order on a BST gives sorted output.
The recursion stack encodes the current path, which is what makes cycle detection and topological sorting natural.
Directed cycle detection needs three states: unvisited, on-stack, finished.
O(V+E) time and O(depth) space — cheaper than BFS on wide graphs, more likely to hit the recursion limit on deep ones.
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.
Check yourself
0 of 3
Answer without scrolling back up.
Without the visited set, DFS on a graph containing a cycle:
A graph is not a tree. The visited set is the only thing that terminates the traversal - the program adds a G to A edge to demonstrate exactly this.
Why does the iterative version also check 'if node in visited' after popping?
Duplicates on the stack are harmless but wasteful; without the check the same node is expanded twice.
Work that belongs on the "leave" line - after the recursive calls return - includes:
Post-order work needs the whole subtree already processed. Topological sort by DFS is exactly this, reversed.
Cheat sheet
Depth First Search
Start at a node and mark it visited. Pick any unvisited neighbour and move there. Repeat. When a node has no unvisited neighbours left, back up to the previous node and try its next neighbour. The search finishes when it has backed all the way out of the start node.
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.