Depth-First Search Algorithm Explained with Examples

By Khaled Md Tuhidul Hossain · 2025-08-28 · Algorithms

If you've ever tried to solve a maze by following one path as far as possible before backtracking, you already understand DFS intuitively. That's literally the strategy. Go deep, hit a dead end, back up, try the next option.

Depth-First Search shows up everywhere in programming. From detecting cycles in dependency graphs to solving puzzles to figuring out if two nodes are connected. It's one of the first graph algorithms worth learning, and honestly one of the most useful.

Interactive visualization

Use the controls below to step through the algorithm or let it play automatically.

name: dfs
input: {"nodes": ["A", "B", "C", "D", "E", "F", "G"], "edges": [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["C", "G"]], "start": "A"}
speed: 700

How DFS actually works

The idea is simple. You start at some node, pick a neighbor, and keep going deeper until you can't anymore. Then you backtrack to the last node that had unexplored neighbors and repeat.

You can implement this with either recursion (which uses the call stack) or an explicit stack data structure. Both give you the same traversal order.

Here's a graph we'll work through:

Starting from node A, DFS visits nodes in this order: A → B → D → H → E → C → F → G

Notice how it goes all the way down through A → B → D → H before it ever touches C. That's the "depth-first" part.

Step-by-step stack walkthrough

Let's trace through the algorithm manually. This is the part that makes everything click.

Here's what happens at each step:

Stack empty. We're done. Every node visited exactly once.

Python implementation

Here's both the iterative and recursive versions. I'd suggest understanding the iterative one first since it makes the stack mechanics explicit.

Iterative DFS (using a stack)

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

    while stack:
        node = stack.pop()
        if node in visited:
            continue

        visited.add(node)
        order.append(node)

        # Add neighbors in reverse order so we visit
        # the first neighbor first (stack is LIFO)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order


# Example graph as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H'],
    'E': [],
    'F': [],
    'G': [],
    'H': []
}

print(dfs_iterative(graph, 'A'))
# Output: ['A', 'B', 'D', 'H', 'E', 'C', 'F', 'G']

Recursive DFS

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()

    visited.add(node)
    print(node, end=' ')

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited

The recursive version is cleaner, but keep in mind Python has a default recursion limit of 1000. For large graphs, either increase it with sys.setrecursionlimit() or just use the iterative version.

DFS on a graph with cycles

Real-world graphs usually have cycles. So you need the visited set to avoid infinite loops. Without it, you'd keep going around in circles forever.

def has_cycle(graph):
    """Detect if a directed graph has a cycle using DFS."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def visit(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True  # Back edge found, cycle exists
            if color[neighbor] == WHITE and visit(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(visit(node) for node in graph if color[node] == WHITE)

The three-color approach is standard for cycle detection. White means unvisited, gray means currently being explored (still on the stack), and black means fully processed. If you hit a gray node, you've found a cycle.

When should you use DFS?

DFS is your go-to when you need to explore all possibilities or when the solution is likely deep in the search space.

Maze solving

Think of each cell as a node and each passable direction as an edge. DFS will follow one path until it hits a wall, then backtrack. It won't find the shortest path, but it will find a path if one exists.

Topological sorting

When you have tasks with dependencies (like build systems or course prerequisites), DFS gives you a valid ordering. You just record nodes in the order they finish processing, then reverse that list.

def topological_sort(graph):
    visited = set()
    result = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    return result[::-1]

Finding connected components

Need to know which nodes can reach each other? Run DFS from an unvisited node, mark everything it touches as one component, then repeat from the next unvisited node.

Path finding in trees

DFS is natural for tree problems. Finding a path between two nodes, checking if a value exists, computing depth. Trees are just graphs without cycles, so DFS works beautifully.

Time and space complexity

Where V is the number of vertices and E is the number of edges.

For dense graphs where E approaches V², the time complexity effectively becomes O(V²). For sparse graphs (like trees where E = V - 1), it's closer to O(V).

DFS vs BFS: quick comparison

Pick DFS when you want to go deep quickly, detect cycles, or do topological sorting. Pick BFS when you need shortest paths in unweighted graphs. They're both O(V + E) in time, so performance isn't the deciding factor. It's about what kind of answer you need.

One practical tip: if your graph is very deep but not very wide, DFS might use less memory than BFS. If it's very wide but shallow, BFS wins on memory. Think about the shape of your data.

That's DFS. Simple concept, tons of applications. Once you've got this down, you'll start seeing it everywhere.