Mastering Depth-First Search in Python
DFS in Python
DFS in Python
Now that you understand the theory behind Depth-First Search, let's translate that into Python. Before we can write the search algorithm, we need a way to represent a graph. A common and efficient method is an adjacency list, which we can implement using a dictionary. Each key in the dictionary will be a node, and its value will be a list of its neighbors.
Here’s how we'd represent the graph above in Python:
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
Recursive Implementation
The recursive approach to DFS is often the most straightforward to write. The logic mirrors the algorithm's definition: visit a node, then recursively call the function for each of its unvisited neighbors. We'll use a set to keep track of visited nodes to avoid getting stuck in cycles and re-processing nodes.
visited = set() # A set to store visited nodes.
def dfs_recursive(graph, node):
if node not in visited:
print(node) # Process the node
visited.add(node)
for neighbor in graph[node]:
dfs_recursive(graph, neighbor)
# Start DFS from node 'A'
dfs_recursive(graph, 'A')
When you run this code, it will print the nodes in one of the possible DFS traversal orders, such as A, B, D, E, F, C. The function explores the 'B' branch completely before backtracking to explore the 'C' branch.
The recursive approach is elegant but can hit Python's recursion depth limit on very large or deep graphs.
Iterative Implementation
An iterative version of DFS avoids recursion by using an explicit stack. This can be more efficient and avoids the risk of a RecursionError. The logic is simple: push the starting node onto a stack. While the stack isn't empty, pop a node, process it if it hasn't been visited, and then push its unvisited neighbors onto the stack.
def dfs_iterative(graph, start_node):
visited = set()
stack = [start_node]
while stack:
node = stack.pop()
if node not in visited:
print(node) # Process the node
visited.add(node)
# Add neighbors to the stack
# Reverse order to mimic recursive version's path
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
Note that we add neighbors to the stack in reverse order. Because a stack is Last-In, First-Out (LIFO), this ensures that we visit them in the same order as the recursive version (e.g., visiting 'B' before 'C').
Special Cases
Let's adapt our DFS function to handle a couple of common scenarios: weighted graphs and cycle detection.
Handling Weighted Graphs
For a weighted graph, DFS itself doesn't change. The algorithm is concerned with connectivity, not the cost of paths. However, you need to adjust your graph representation to store the weights. You might use a list of tuples for the adjacency list, where each tuple is
(neighbor, weight).
graph_weighted = {
'A': [('B', 5), ('C', 3)],
'B': [('D', 2), ('E', 8)],
'C': [('F', 4)],
'D': [],
'E': [('F', 1)],
'F': []
}
# The DFS traversal logic remains the same, but now
# you have access to weights when you iterate neighbors.
# Example modification:
def dfs_recursive_weighted(graph, node):
if node not in visited:
visited.add(node)
print(f"Visiting node: {node}")
for neighbor, weight in graph[node]:
print(f" -> to {neighbor} with weight {weight}")
dfs_recursive_weighted(graph, neighbor)
Detecting Cycles
A powerful use of DFS is to detect cycles in a directed graph. The trick is to keep track not just of visited nodes, but also of nodes currently in the recursion stack (the path we are currently exploring). If we encounter a node that's already in our current recursion path, we've found a cycle.
To do this, we can use two sets: visited to track all nodes ever visited, and recursion_stack for nodes in the current path.
def has_cycle(graph):
visited = set()
recursion_stack = set()
def cycle_check(node):
visited.add(node)
recursion_stack.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if cycle_check(neighbor):
return True
elif neighbor in recursion_stack:
# Found a back edge to a node in the current path
return True
# Backtrack: remove node from recursion stack
recursion_stack.remove(node)
return False
# Check for cycles starting from every node
for node in graph:
if node not in visited:
if cycle_check(node):
return True
return False
# Example of a graph with a cycle: A -> B -> C -> A
cyclic_graph = {
'A': ['B'],
'B': ['C'],
'C': ['A']
}
print(f"Does the graph have a cycle? {has_cycle(cyclic_graph)}")
This implementation uses a helper function to manage the recursion and correctly tracks the state of each node. By the end, you'll know if a cycle exists anywhere in the graph.
Which Python dictionary correctly represents a directed graph where node 'X' points to 'Y' and 'Z', and 'Y' also points to 'Z'?
In a recursive Depth-First Search implementation, what is the primary purpose of maintaining a visited set?
With these patterns, you can implement DFS in Python and adapt it to solve a variety of graph-based problems.