Implementation of DFS Algorithm in Python

Depth First Search (DFS) is a powerful tool for exploring graphs, and understanding how to implement it is key to solving many computer science problems. In this article, we’ll focus on how to write a DFS algorithm in Python.

Tip

Before diving into the implementation, it’s helpful to have a good understanding of what graphs are and the basic idea behind Depth First Search. You can learn more about them in these articles:

Representing a Graph in Python

Before we can implement DFS, we need a way to represent our graph in Python. Two common ways to do this are using an adjacency list or an adjacency matrix.

Adjacency List

An adjacency list represents the graph as a dictionary where each key is a node, and its value is a list of its neighboring nodes. This is efficient for sparse graphs (graphs with fewer connections).

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

Adjacency Matrix

An adjacency matrix represents the graph as a 2D array (a list of lists) where matrix[i][j] = 1 if there’s an edge from vertex i to vertex j, and 0 otherwise. It’s simpler to implement but uses more memory, especially for sparse graphs.

# In this example, let's assume nodes are 0, 1, 2, 3, 4, 5, corresponding to A, B, C, D, E, F
# Matrix must be square (NxN) where N is the number of nodes
matrix = [
    [0, 1, 1, 0, 0, 0],  # A
    [0, 0, 0, 1, 1, 0],  # B
    [0, 0, 0, 0, 0, 1],  # C
    [0, 0, 0, 0, 0, 0],  # D
    [0, 0, 0, 0, 0, 1],  # E
    [0, 0, 0, 0, 0, 0]   # F
]

In this article, we will focus on representing graphs using the adjacency list, as it’s often more efficient for DFS.

Recursive DFS Implementation

The most common and intuitive way to implement DFS is using recursion. Here’s how it works:

  1. Mark the current node as visited. We use a set called visited to keep track of visited nodes.
  2. Process the current node. This could involve printing the node’s value, adding it to a list, or performing any other action.
  3. Explore the neighbors. For each neighbor of the current node:
    • If the neighbor hasn’t been visited yet, recursively call the DFS function on that neighbor.

Here’s the Python code for the recursive DFS:

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set() # Initialize visited set, or function can't be re-run properly

    if node not in visited:
        visited.add(node)
        print(node, end=' ')  # Process the node (e.g., print it)

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

Here’s how you might use this function:

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

print("DFS Traversal (Recursive):")
dfs_recursive(graph, 'A')  # Start DFS from node 'A'
print()  # Add a newline for clarity
# Expected output (order may vary depending on neighbor order in the dict):
# DFS Traversal (Recursive):
# A B D E F C
  • The function dfs_recursive takes the graph, the current node, and a visited set as input.
  • If visited is None (not provided in the initial call), we create an empty set to store visited nodes.
  • We check if the current node is in the visited set. If it’s not, we add it to the set and process it (in this case, print it).
  • Then, we iterate through the neighbors of the current node and recursively call dfs_recursive for each unvisited neighbor.

Iterative DFS Implementation using a Stack

An alternative to recursion is to use an iterative approach with a stack. This can be helpful to avoid recursion depth limits.

Here’s the iterative approach:

  1. Create a stack and add the starting node to it.
  2. Create a set to keep track of visited nodes.
  3. While the stack is not empty:
    • Pop a node from the stack.
    • If the node hasn’t been visited:
      • Mark it as visited.
      • Process the node (e.g., print it).
      • Add all its unvisited neighbors to the stack.

Here’s the Python code for the iterative DFS:

def dfs_iterative(graph, start_node):
    visited = set()  # Keep track of visited nodes
    stack = [start_node]  # Use a list as a stack

    print("DFS Traversal (Iterative):")
    while stack:
        node = stack.pop()  # Pop the top node

        if node not in visited:
            visited.add(node)
            print(node, end=' ')  # Process the node

            # Add neighbors to the stack in reverse order to maintain DFS order
            neighbors = list(graph[node])  # Create a list copy to avoid modifying the original graph
            for neighbor in reversed(neighbors):
                if neighbor not in visited:
                    stack.append(neighbor)

    print()  # Add a newline for clarity

Here’s how you might use this function:

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

dfs_iterative(graph, 'A')
# Possible output (order might differ slightly from recursive):
# DFS Traversal (Iterative):
# A C F B E D
  • We initialize a visited set and a stack.
  • We push the start_node onto the stack.
  • The while loop continues as long as there are nodes in the stack.
  • Inside the loop, we pop a node from the stack. This is the node we’ll explore next.
  • If the node hasn’t been visited, we mark it as visited and process it.
  • We find all neighbors of the current node. For each neighbor that hasn’t been visited yet, we append it to the stack.
  • Note that we are iterating the neighbors in reversed order so that the visit sequence match closer to the recursive version of DFS.

Choosing Between Recursive and Iterative

  • Recursive DFS: Is often simpler to write and understand, closely matching the definition of DFS. However, it can lead to a stack overflow error if the graph is very deep.
  • Iterative DFS: Is more robust against deep graphs, as it uses heap memory for the stack. The logic might feel slightly less direct than recursion.

Both implementations have a time complexity of O(V + E), where V is the number of vertices (nodes) and E is the number of edges. The space complexity is O(V) in the worst case, as we need to store all vertices in the visited set and the stack (in the iterative version) or the call stack (in the recursive version). You can refer to this article to dive deeper into the time and space complexity of DFS.

What’s Next?

Now that you’ve learned how to implement DFS in Python, you can explore other related articles: