Python Program to Implement Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible down each branch before backtracking. It's used for things like detecting cycles, solving mazes, topological sorting, and finding connected components — and it's a near-guaranteed interview topic for anyone working with graphs or trees.

This post represents a graph as an adjacency dictionary (each node maps to a list of its neighbors) and implements DFS two ways: recursively, and iteratively using an explicit stack.

Python Program for Recursive DFS

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


def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = []
    if node not in visited:
        visited.append(node)
        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)
    return visited


print("DFS (recursive):", dfs_recursive(graph, "A"))

Output:

DFS (recursive): ['A', 'B', 'D', 'E', 'F', 'C']

---

Python Program for Iterative DFS Using a Stack

Deep graphs can hit Python's recursion limit, so it's worth knowing the iterative version too — it uses an explicit stack (a plain list) instead of the call stack.

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

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            # Push neighbors in reverse so the traversal order matches the recursive version
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return visited


print("DFS (iterative):", dfs_iterative(graph, "A"))

Output:

DFS (iterative): ['A', 'B', 'D', 'E', 'F', 'C']

Both versions run in O(V + E) time, where V is the number of vertices and E is the number of edges, since every node and edge is visited at most once. The visited list also doubles as cycle protection — without it, a graph with a cycle would send either version into an infinite loop. For shortest-path-style problems instead of "can I reach this node," Breadth-First Search (BFS) is usually the better fit, since it explores level by level.

---