Depth First Search Algorithm Explained
DFS in Python
Recursive DFS in Python
The “go as deep as possible” nature of Depth First Search makes recursion a natural fit. We can write a function that calls itself to explore each new branch. You’ve already learned the principles of DFS; now let’s translate that into Python code.
We'll represent our graph using an adjacency list, which is easy to implement in Python with a dictionary. Each key will be a node, and its value will be a list of its neighbors.
To avoid infinite loops in graphs with cycles, we need to keep track of the nodes we've already visited. A Python set is perfect for this because it provides fast lookups.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set() # A set to keep track of visited nodes.
def dfs_recursive(visited, graph, node):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbour in graph[node]:
dfs_recursive(visited, graph, neighbour)
# Start DFS from node 'A'
dfs_recursive(visited, graph, 'A')
# Expected output: A B D E F C
The logic is straightforward. If we encounter a node that isn't in our visited set, we print it, add it to the set, and then recursively call the function for each of its neighbors. This process continues until it hits a dead end (a node with no unvisited neighbors), at which point it backtracks to the previous node and explores its next neighbor.
Iterative DFS in Python
While elegant, recursion can cause a "stack overflow" error if the graph is very deep. The system's call stack, which keeps track of active function calls, can run out of space. To avoid this, we can implement DFS iteratively using our own stack.
A stack follows a Last-In, First-Out (LIFO) principle. In Python, a list can serve as a simple stack, using append() to push items on top and pop() to remove them.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
def dfs_iterative(graph, start_node):
visited = set()
stack = [start_node]
while stack:
vertex = stack.pop() # Get the last node added
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
# Add neighbors to the stack
# Note: They are added in reverse order of exploration
for neighbour in reversed(graph[vertex]):
stack.append(neighbour)
# Start DFS from node 'A'
dfs_iterative(graph, 'A')
# Expected output: A B D E F C
Here, we initialize a stack with the starting node. The while loop continues as long as there are nodes in the stack to visit. We pop a node, and if we haven't seen it before, we process it and add its neighbors to the top of the stack. We add neighbors in reverse order so that the first neighbor in the adjacency list is the first one to be processed, mimicking the typical recursive behavior.
Advanced Scenarios
What happens if a graph isn't fully connected? The basic DFS functions we wrote would only traverse the component containing the start node, leaving other parts of the graph unexplored. To handle this, we can create a wrapper function that iterates through every node in the graph, starting a DFS traversal only if a node hasn't been visited yet.
# An example of a disconnected graph
disconnected_graph = {
'A': ['B'],
'B': ['A'],
'C': ['D'],
'D': ['C']
}
def dfs_full_graph(graph):
visited = set()
for node in graph:
if node not in visited:
# Start a new DFS traversal for an unvisited component
dfs_recursive(visited, graph, node)
dfs_full_graph(disconnected_graph)
# Expected output: A B C D (or C D A B, depending on dictionary order)
This approach ensures that every node in every connected component of the graph is visited exactly once.
Another common task is detecting cycles. A cycle exists if we visit a node that is currently in our recursion path. We can detect this by keeping track of the nodes in the current "recursion stack" in addition to the globally visited nodes.
Here’s how to modify the recursive DFS to detect a cycle in a directed graph. We'll use a set called recursion_stack to track the nodes on the current path.
def has_cycle_util(graph, node, visited, recursion_stack):
visited.add(node)
recursion_stack.add(node)
for neighbour in graph[node]:
if neighbour not in visited:
if has_cycle_util(graph, neighbour, visited, recursion_stack):
return True
elif neighbour in recursion_stack:
# If the neighbor is in the recursion stack, we found a cycle
return True
# Remove the node from the recursion stack before returning
recursion_stack.remove(node)
return False
def has_cycle(graph):
visited = set()
recursion_stack = set()
for node in graph:
if node not in visited:
if has_cycle_util(graph, node, visited, recursion_stack):
return True
return False
# Example graph with a cycle
cyclic_graph = { 'A': ['B'], 'B': ['C'], 'C': ['A'] }
print(f"\nDoes it have a cycle? {has_cycle(cyclic_graph)}") # True
When we explore a node, we add it to both visited and recursion_stack. If we encounter a neighbor that is already in the recursion_stack, it means we've found a "back edge," indicating a cycle. Once we're done exploring all paths from a node, we remove it from recursion_stack before backtracking. This is crucial; it signifies that this node is no longer in the current path.
When implementing a recursive Depth First Search in Python, what two data structures are essential for representing the graph and preventing infinite loops?
What is the primary drawback of using a purely recursive approach for DFS, especially on a graph with very long paths?