While Breadth-First Search (BFS) goes through a graph layer by layer, Depth-First Search (DFS) takes a different approach. As the name suggests, DFS goes as far as possible along each branch before backtracking. Think of it like navigating a maze: you follow one path until you hit a dead end, then you backtrack to the last junction and try a different unexplored path. This strategy is important for various graph algorithms used in analyzing network structures and dependencies.
DFS typically starts at an arbitrary node (often called the 'source' or 'root' for the search) and explores along a path. Here's the general process:
Unlike BFS which uses a queue to manage nodes to visit, DFS naturally uses a stack. This stack can be the program's call stack (in a recursive implementation) or an explicit stack data structure (in an iterative implementation).
Recursion provides an elegant way to implement DFS. The function calls itself for each unvisited neighbor, effectively using the call stack to manage the backtracking process.
Let's assume our graph is represented using an adjacency list (a dictionary where keys are nodes and values are lists of neighbors).
import collections
def dfs_recursive(graph, node, visited):
"""
Performs Depth-First Search recursively starting from 'node'.
Args:
graph (dict): Adjacency list representation of the graph.
Example: {'A': ['B', 'C'], 'B': ['D'], ...}
node: The starting node for the current DFS exploration.
visited (set): A set keeping track of visited nodes.
Returns:
None. Modifies the 'visited' set in place.
"""
if node not in visited:
print(f"Visiting node: {node}") # Process the node (e.g., print)
visited.add(node)
if node in graph: # Check if the node has neighbors
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# Example Usage:
graph_adj = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("Recursive DFS starting from node A:")
visited_nodes_rec = set()
dfs_recursive(graph_adj, 'A', visited_nodes_rec)
print("Visited nodes:", visited_nodes_rec)
# Handling disconnected graphs (if necessary)
# You would iterate through all nodes and start DFS if not visited
# all_nodes = list(graph_adj.keys()) # Or however you get all nodes
# visited_all = set()
# for node in all_nodes:
# if node not in visited_all:
# print(f"\nStarting new DFS component from {node}")
# dfs_recursive(graph_adj, node, visited_all)
The recursive approach mirrors the definition of DFS: visit a node, then recursively visit its unvisited neighbors one by one.
While recursion is often intuitive for DFS, it can lead to stack overflow errors for very deep graphs. An iterative approach using an explicit stack avoids this limitation.
import collections
def dfs_iterative(graph, start_node):
"""
Performs Depth-First Search iteratively using a stack.
Args:
graph (dict): Adjacency list representation of the graph.
start_node: The node to begin the search from.
Returns:
set: A set containing all nodes visited during the search.
"""
if start_node not in graph:
print(f"Start node {start_node} not in graph.")
return set()
visited = set()
stack = collections.deque([start_node]) # Use deque as a stack
print("Iterative DFS starting from node A:")
while stack:
node = stack.pop() # Get the last added node (LIFO)
if node not in visited:
print(f"Visiting node: {node}") # Process the node
visited.add(node)
# Add unvisited neighbors to the stack
# Add neighbors in reverse order to visit them in standard order
# (though order doesn't strictly matter for correctness)
if node in graph:
# Process neighbors in reverse to mimic recursion order if needed
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return visited
# Example Usage (using the same graph_adj as before):
visited_nodes_iter = dfs_iterative(graph_adj, 'A')
print("Visited nodes:", visited_nodes_iter)
In the iterative version, we push the starting node onto the stack. Then, while the stack is not empty, we pop a node, visit it (if not already visited), and push its unvisited neighbors onto the stack. The use of collections.deque is common in Python for efficient stack operations (append and pop from the same end). Note that the order in which neighbors are pushed onto the stack affects the specific DFS path taken, but the set of visited nodes from a starting point will ultimately be the same.
Consider the following simple graph. Let's trace the DFS path starting from node 'A', assuming neighbors are explored in alphabetical order.
A possible DFS traversal starting from node A (exploring neighbors alphabetically): A -> B -> D -> E -> F -> C -> G. The red node is the start. Pink edges with numbers show the order of exploration into unvisited nodes.
The path goes deep: A to B, B to D. D has no unvisited neighbors, so backtrack to B. B's next unvisited neighbor is E. Go A -> B -> E. E's next unvisited neighbor is F. Go A -> B -> E -> F. F's neighbors (C, E, A) have all been visited or are on the current path back to the start, so backtrack to E, then B, then A. A's next unvisited neighbor is C. Go A -> C. C's next unvisited neighbor is F (already visited). C's next unvisited neighbor is G. Go A -> C -> G. G has no unvisited neighbors. Backtrack to C, then A. All neighbors of A are visited. DFS completes. The visited order would be A, B, D, E, F, C, G.
visited set, which takes space.
Therefore, the overall space complexity is typically dominated by the stack or recursion depth, resulting in .DFS's property of exploring deeply makes it suitable for several graph-related tasks often encountered in machine learning contexts:
Understanding DFS provides another essential tool for navigating and analyzing the graph structures that underpin many machine learning problems, from feature dependencies to network analysis and recommendation systems.
Was this section helpful?
© 2026 ApX Machine LearningEngineered with