Implementing Depth-First Search (DFS) Algorithm in Python

In this blog, we'll walk through the implementation of Depth-First Search (DFS) in Python, covering both recursive and iterative approaches. We'll use an adjacency list representation for our graph, which is a common way to represent graphs in Python.

What is Depth-First Search (DFS) Algorithm?

Depth-First Search (DFS) is a traversal algorithm that explores as deep as possible along each branch before backtracking. It starts at a selected node (often called the “root” in trees or a starting point in graphs) and explores each branch fully before moving on to the next one. This depth-oriented behavior contrasts with Breadth-First Search (BFS), which explores nodes level by level.

DFS can be implemented using either recursion or an explicit stack, and it works for both connected and disconnected graphs.

The core idea behind DFS is simple: go as deep as you can, then backtrack when there’s nowhere left to go.

Here’s the general flow:

1. Start at the source node.

2. Mark the node as visited.

3. Explore one of its unvisited neighbors.

4. Repeat the process recursively (or using a stack) until you reach a node with no unvisited neighbors.

5. Backtrack to explore other branches.

   
   

DFS can be recursive, which mimics the call stack naturally, or iterative, using an explicit stack data structure.

DFS is more than just a traversal algorithm — it’s a foundation for solving many important computer science problems:

1. Pathfinding: Finding paths in mazes or game maps.

2. Cycle Detection: Detecting cycles in directed or undirected graphs.

3. Topological Sorting: Ordering tasks in DAGs (Directed Acyclic Graphs).

4. Connected Components: Identifying isolated groups in a graph.

5. Solving Puzzles: Such as Sudoku, mazes, and word ladders.

6. Tree Traversals: Preorder, Inorder, and Postorder traversals in binary trees are variations of DFS.

   
   

Depth First Search(DFS) Algorithm Steps

Here’s a high-level overview of how DFS is typically implemented:

Recursive Version

1. Start from a source node.

2. Mark it as visited.

3. For each neighbor:

   • If not visited, call DFS on that neighbor.

4. Repeat until all nodes are visited.

   
   

Iterative Version (using a stack)

1. Push the starting node onto a stack.

2. While the stack is not empty:

   • Pop the top node.

   • If not visited:

     • Mark as visited.

     • Push all unvisited neighbors onto the stack.

       
       

Both versions achieve the same result, but the iterative version is often preferred in environments where recursion depth is a concern.

Graph Representation

We'll start by representing our graph using an adjacency list. In Python, an adjacency list can be implemented using a dictionary where keys represent nodes and values are lists of adjacent nodes.

---

# Graph representation using an adjacency list

graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F'],

    'D': ['B'],

    'E': ['B', 'F'],

    'F': ['C', 'E']

}

---

Depth-First Search (DFS) Algorithm in Python

Depth-First Search (DFS) in Python is a classic graph traversal algorithm used to explore nodes and edges of a graph by diving as deep as possible into the graph before backtracking. Starting from a given source node, DFS explores each branch of the graph recursively or iteratively until it reaches the end of a branch. In Python, DFS can be implemented using either recursion or a stack data structure. When using recursion, the algorithm visits a node, processes it, and then recursively visits all its unvisited neighbors. If implemented iteratively, a stack is used to manage the nodes to be explored, pushing each unvisited neighbor onto the stack as it traverses the graph. DFS is particularly useful for tasks such as finding connected components, solving puzzles, and topological sorting. Its ability to explore deeply and backtrack efficiently makes it a valuable algorithm for various computational problems in Python.

Recursive Depth-First Search (DFS) Algorithm in Python Implementation

The recursive approach to DFS is elegant and straightforward. The idea is to explore each branch of the graph recursively, marking nodes as visited to avoid cycles.

---

def dfs_recursive(graph, node, visited=None):

     if visited is None:

         visited = set()

     # Mark the node as visited

     visited.add(node)

     print(node, end=' ')

     # Explore each adjacent node

     for neighbor in graph[node]:

         if neighbor not in visited:

             dfs_recursive(graph, neighbor, visited)

     return visited

# Run DFS starting from node 'A'

print("DFS (Recursive):")

dfs_recursive(graph, 'A')

---

Output of the code above:

DFS (Recursive):
A B D E F C 
{'A', 'B', 'C', 'D', 'E', 'F'}

This recursive DFS implementation starts by checking if the visited set exists; if not, it initializes one to keep track of visited nodes. It then marks the current node as visited, prints it, and recursively explores all unvisited neighbors in the graph. The function continues to dive deeper into each branch until all reachable nodes from the starting point have been visited. This approach is simple and elegant, leveraging Python’s call stack to manage the traversal path.

Iterative Depth-First Search (DFS) Algorithm in Python Implementation

The iterative approach uses a stack to manage the nodes to be explored. This method avoids the recursion limit issues of the recursive approach, making it suitable for large graphs.

---

def dfs_iterative(graph, start):

     visited = set()

     stack = [start]

     while stack:

        node = stack.pop()

         if node not in visited:

             visited.add(node)

             print(node, end=' ')

             # Add all unvisited neighbors to the stack

             stack.extend(neighbor for neighbor in graph[node] if neighbor not in  visited)

     return visited

# Run DFS starting from node 'A'

print("\nDFS (Iterative):")

dfs_iterative(graph, 'A')

---

Output of the code above:

DFS (Iterative):
A C F E B D 
{'A', 'B', 'C', 'D', 'E', 'F'}

This iterative DFS implementation uses an explicit stack to manage the traversal order, simulating what recursion does behind the scenes. It begins at the given start node and continues while the stack is not empty. At each step, it pops a node from the stack, marks it as visited if it hasn't been already, and prints it. It then adds all of its unvisited neighbors to the stack for further exploration. This approach gives you more control over the traversal process and avoids recursion depth limitations, making it more suitable for very large or deeply nested graphs.

Conclusion

Depth-First Search (DFS) is a versatile and essential algorithm for traversing graphs and trees. Its ability to explore deep into data structures makes it particularly useful for problems where you need to investigate one path fully before considering alternatives. From finding paths in mazes to detecting cycles in graphs and solving complex puzzles, DFS offers a systematic approach to exploring all possible options in a structured manner.

By mastering both recursive and iterative implementations, you gain the flexibility to apply DFS in different contexts. Recursive DFS is concise and elegant, often easier to understand for small graphs or trees. On the other hand, the iterative version—using an explicit stack—is better suited for large or deep graphs where recursion might cause stack overflow errors.

Whether you’re building AI for games, analyzing social networks, or working on compiler design, DFS remains a fundamental and powerful tool in your programming toolkit. Understanding how and when to use it is key to solving a wide range of algorithmic challenges efficiently.