Learn how DFS explores a graph by going as deep as possible before backtracking, using recursion or an explicit stack.

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible down one path before backtracking and trying another. It uses a stack to track where to backtrack to — either an explicit stack, or implicitly through recursion (which uses the call stack).

Depth-First Searchstack · dive deep first

stack (LIFO)

top →A

visit order

empty

dfs.py

def dfs_iterative(graph, start):

visited = set(); stack = [start]

while stack:

vertex = stack.pop()

if vertex in visited: continue

visited.add(vertex)

for neighbor in graph[vertex]:

if neighbor not in visited: stack.append(neighbor)

Start DFS from A. stack = [A]

step 0/14

Recursive DFS

The most natural way to write DFS — the function calls itself on each unvisited neighbor.

def dfs(graph, vertex, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []

    visited.add(vertex)
    order.append(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)

    return order


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

print(dfs(graph, "A"))   # ['A', 'B', 'D', 'E', 'F', 'C']

Iterative DFS — using an explicit stack

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()   # take the most recently added

        if vertex in visited:
            continue

        visited.add(vertex)
        order.append(vertex)

        # push neighbors — they'll be explored before anything pushed earlier
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                stack.append(neighbor)

    return order


print(dfs_iterative(graph, "A"))   # similar order, may vary slightly

The recursive version is usually preferred for readability — Python's call stack handles the backtracking automatically. The iterative version with an explicit stack avoids Python's recursion depth limit (default 1000), which matters for very deep or large graphs.

Why a stack, not a queue

A stack always processes the most recently discovered vertex next — pushing the exploration deeper and deeper down one branch before ever coming back to try a sibling branch. This is the opposite of BFS, where the queue forces breadth-first, level-by-level exploration.

Stack:  [A]              pop A, push B, C → stack = [B, C]
        [B, C]           pop C, push F   → stack = [B, F]
        [B, F]           pop F, push E   → stack = [B, E]
        [B, E]           pop E, nothing new (B visited) → stack = [B]
        [B]              pop B, push D   → stack = [D]
        [D]              pop D, nothing new → stack = []

Result: A, C, F, E, B, D — notice how it dove all the way down through C → F → E before ever returning to B.

Detecting a cycle with DFS

DFS can detect cycles by tracking which vertices are currently "in progress" — on the current path being explored — versus fully finished.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2   # unvisited, in progress, done
    color = {v: WHITE for v in graph}

    def visit(vertex):
        color[vertex] = GRAY   # mark as in progress

        for neighbor in graph[vertex]:
            if color[neighbor] == GRAY:
                return True   # found a back edge — cycle!
            if color[neighbor] == WHITE and visit(neighbor):
                return True

        color[vertex] = BLACK   # mark as fully done
        return False

    for vertex in graph:
        if color[vertex] == WHITE:
            if visit(vertex):
                return True

    return False

If DFS reaches a vertex that is still "in progress" (gray) on the current path, that means there is a path back to an ancestor — a cycle.

Finding all connected components

def connected_components(graph):
    visited = set()
    components = []

    for vertex in graph:
        if vertex not in visited:
            # new component — DFS from here collects everything reachable
            component = dfs(graph, vertex, set(), [])
            visited.update(component)
            components.append(component)

    return components

DFS vs BFS — when to use which

Goal	Use
Shortest path (unweighted)	BFS
Does a path exist at all	Either
Detect a cycle	DFS
Find connected components	Either
Explore all possibilities (backtracking)	DFS
Topological sort	DFS
Find nodes "close" to start	BFS
Memory-constrained, very deep graph	DFS (less memory per level)
Very wide graph, many neighbors per node	BFS may use more memory

BFS finds the shortest path because it explores breadth-first — level by level. DFS does not guarantee shortest path because it commits fully to one direction before backtracking — it might find a long, winding path to the target long before it tries the short direct route.

Real use cases

Maze solving — DFS explores one path fully before backtracking, similar to how a person might explore a maze.

Topological sorting — ordering tasks with dependencies, like course prerequisites or build systems.

Cycle detection — detecting circular dependencies in package managers or deadlocks in resource allocation.

Finding connected components — identifying clusters or islands in a graph.

Solving puzzles with backtracking — Sudoku solvers, N-Queens, generating all permutations.

Complexity

	Time	Space
DFS (recursive)	O(V + E)	O(V) — call stack depth
DFS (iterative)	O(V + E)	O(V) — explicit stack

Same asymptotic complexity as BFS — the difference is purely in exploration order, not efficiency.

Depth-First Search (DFS)

On this page