Graphs — Visual Learning

DFS Visualization —
Dive deep, then backtrack.

Depth-First Search commits to one path and follows it as far as it can go before backtracking to try another branch — powered by recursion or an explicit stack. It's the natural choice for "does a path exist," cycle detection, and exploring every connected node. Watch the recursion dive to a dead end and unwind on LearnBug, one backtrack at a time.

O(V+E)Time complexity
O(V)Space complexity
PythonLanguage

What is DFS?

From a node, visit an unvisited neighbor, then immediately recurse into that neighbor's unvisited neighbor, and so on — going as deep as possible before backtracking. When a node has no unvisited neighbors left, the recursion returns to whichever call is still waiting to try its next neighbor.

Why visualization helps

The backtrack step is the part that's invisible in code — a function just returns, and control silently resumes at the caller. LearnBug highlights the current node and shows the call stack shrinking on every backtrack, so "dead end, go back and try the next branch" is something you watch instead of infer.

YouTube — DFS Explained Visually
📺 Drop your YouTube embed here
LearnBug — recursion diving deep, then backtracking
🖼 Add a LearnBug screenshot here
Two Ways to DFS

Recursive call stack vs explicit stack

Recursive

Python's own call stack tracks where to backtrack to. Concise, but limited by Python's recursion depth on very deep graphs.

Call stack

Iterative

An explicit stack replaces recursion — same LIFO behavior, no recursion-depth limit, but visit order can differ slightly depending on push order.

Explicit stack

Cycle detection

DFS with a "currently in recursion stack" marker is the standard way to detect a cycle in a directed graph — see the next lesson.

Back edges
Walkthrough

DFS from A on A→[B,C], B→[D], C→[D]

1

Visit A, recurse into its first unvisited neighbor B

A has two neighbors, B and C. DFS commits to the first one — B — and dives into it immediately, without looking at C yet.

Avisit
B
C
D
Call stack: dfs(A) → dfs(B)  |  Visited: [A]
2

Visit B, recurse into its only neighbor D — still diving

B has one neighbor, D, which is unvisited. DFS keeps diving deeper instead of backtracking to try C yet.

A
Bvisit
C
D
Call stack: dfs(A) → dfs(B) → dfs(D)  |  Visited: [A, B]
3

Visit D — dead end, no unvisited neighbors — backtrack all the way to A

D has no neighbors, so dfs(D) returns immediately. dfs(B) has no more neighbors either, so it also returns. Control lands back in dfs(A), ready to try C.

A
B
C
Dvisit
Backtrack: dfs(D) returns → dfs(B) returns → back in dfs(A)  |  Visited: [A, B, D]
4

Back in dfs(A), recurse into C — D is already visited, so it's skipped

C's only neighbor is D, but D is already in the visited set, so dfs(C) does nothing further and returns. The full traversal is done.

Return: [A, B, D, C] ✓ dove all the way down one branch before trying the other

Python Code

Recursive and iterative DFS

PythonRecursive — O(V+E) time, O(V) call stack worst case
graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}
visited = []

def dfs(node):
    if node in visited:
        return
    visited.append(node)     # visit
    for neighbor in graph[node]:
        dfs(neighbor)         # dive before trying the next neighbor
PythonIterative — explicit stack, same O(V+E) / O(V)
def dfs_iterative(start):
    stack, visited, order = [start], [], []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.append(node)
        order.append(node)
        # push in reverse so the FIRST neighbor is popped FIRST
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

Complexity Notes

TimeO(V+E)Every vertex visited once, every edge examined once
SpaceO(V)Call stack (recursive) or explicit stack, worst case one entry per vertex
Not shortest pathNo guaranteeDFS finds *a* path, not the shortest one — use BFS for fewest edges
Recursion limitWatch outVery deep/large graphs can hit Python's recursion limit — use the iterative version

Frequently asked questions

When should I use DFS instead of BFS?

Use DFS when you need to know if a path exists, need to explore every node of a connected component, or need to detect cycles — you don't care about finding the shortest path. Use BFS specifically when "fewest edges" or "minimum steps" matters.

Why does the iterative version push neighbors in reverse order?

A stack is LIFO, so whatever is pushed last gets popped first. To visit neighbors in the same left-to-right order the recursive version naturally follows, you push them in reverse — so the first neighbor in the list ends up on top of the stack and gets popped first.

Can DFS get stuck in an infinite loop?

Only if you forget the visited check. Without it, a cycle in the graph (A → B → A) would cause DFS to recurse forever. The visited list/set is not optional — it's what guarantees termination on graphs with cycles.

Does the order DFS visits nodes matter for correctness?

For "does a path exist" or "find all connected nodes," no — any valid DFS order reaches the same set of nodes. For problems like topological sort or cycle detection, the specific structure of the recursion (not just the order) is what the algorithm relies on.

Watch the recursion dive deep, then backtrack

Paste your DFS into LearnBug and see the call stack grow and shrink at every step.

Open Playground →

Related topics

BFS Visualization — the breadth-first counterpart →Detect Cycle in Graph — DFS-based →Topological Sort — ordering with DFS or BFS →BFS vs DFS — Interview →