When you begin learning algorithms, one of the most interesting and widely used techniques you’ll come across is Depth-First Search (DFS). It’s a simple yet powerful graph traversal algorithm that explores as far as possible along each branch before backtracking. Think of it as diving deep into one path before coming back up to explore others.
with hands-on learning.
get the skills and confidence to land your next move.
Depth-First Search plays an important role in solving many computer science problems. It’s used for exploring graphs and trees, detecting cycles, pathfinding in mazes, solving puzzles like Sudoku, and even in artificial intelligence for exploring game states. What makes DFS so fascinating is its recursive nature and simplicity—it’s like giving a computer a map and telling it to go as deep as it can before turning back.
In this guide, we’ll explore multiple Python programs to implement Depth-First Search using both recursion and iteration. You’ll see how the algorithm works step by step and how you can modify it for different applications.
Program 1: Recursive Implementation of DFS
This first example demonstrates the most straightforward way to implement DFS using recursion. It’s easy to understand and closely matches the definition of DFS.
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# Example graph represented as an adjacency list
graph = {
0: [1, 2],
1: [3],
2: [4],
3: [],
4: []
}
print("Depth-First Search starting from node 0:")
dfs_recursive(graph, 0)In this program, the graph is represented as a dictionary where each node maps to a list of its neighbors. The recursive dfs_recursive() function starts from a given node, prints it, marks it as visited, and then explores its unvisited neighbors. Beginners will find this version easy to grasp because it mirrors how DFS is explained in theory—exploring deeply one branch at a time before backtracking.
Program 2: Iterative DFS Using Stack
While recursion is elegant, Python has a recursion limit, and large graphs might cause a stack overflow. To handle this, we can use an explicit stack to simulate recursion iteratively.
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in reversed(graph.get(node, [])):
if neighbor not in visited:
stack.append(neighbor)
graph = {
0: [1, 2],
1: [3],
2: [4],
3: [],
4: []
}
print("Iterative DFS starting from node 0:")
dfs_iterative(graph, 0)Here, a stack is used to keep track of nodes to visit next. We start from the initial node, visit it, and push its neighbors onto the stack. The algorithm continues until the stack becomes empty. This version gives you more control over the process and avoids recursion depth issues. It also helps beginners understand how recursion can be replaced by a stack for better memory management.
Program 3: DFS for Directed Graphs
In real applications, many graphs are directed, meaning edges have directions (for example, a web link from one page to another). DFS can easily handle directed graphs with a slight modification.
def dfs_directed(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs_directed(graph, neighbor, visited)
graph = {
0: [1],
1: [2],
2: [3],
3: []
}
print("DFS traversal of directed graph starting from node 0:")
dfs_directed(graph, 0)This example performs DFS on a directed graph where edges only go in one direction. The algorithm works exactly the same, but now each edge is only followed in the direction it points. Directed DFS is useful for applications such as analyzing one-way relationships, like following links between web pages or dependencies between software components.
Program 4: DFS for Connected Components in an Undirected Graph
DFS can be extended to find all connected components in an undirected graph. This program shows how to use DFS to explore all nodes and identify separate connected subgraphs.
def dfs_connected_components(graph):
visited = set()
components = []
def dfs(node, component):
visited.add(node)
component.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, component)
for node in graph:
if node not in visited:
component = []
dfs(node, component)
components.append(component)
return components
graph = {
'A': ['B'],
'B': ['A'],
'C': ['D'],
'D': ['C'],
'E': []
}
components = dfs_connected_components(graph)
print("\nConnected components in the graph:", components)Here, DFS is used to explore each unvisited node fully and collect all nodes reachable from it. Beginners can understand how DFS helps identify distinct groups in a graph, which is important for analyzing network connectivity and solving real-world problems.
Program 5: DFS Using Adjacency Matrix
Graphs can also be represented as adjacency matrices, where each element (i, j) indicates whether there is a connection between node i and node j. This method is often used for dense graphs.
def dfs_matrix(graph, node, visited):
visited[node] = True
print(node, end=" ")
for i in range(len(graph)):
if graph[node][i] == 1 and not visited[i]:
dfs_matrix(graph, i, visited)
graph = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 0],
[1, 0, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 0]
]
visited = [False] * len(graph)
print("DFS traversal using adjacency matrix starting from node 0:")
dfs_matrix(graph, 0, visited)This version of DFS is based on a 2D matrix representation. The function checks each possible connection and recursively visits nodes that are directly connected and not yet visited. Although this approach takes more memory, it’s ideal for graphs where most nodes are interconnected.
Program 6: DFS with User Input
To make DFS more interactive and practical, this version lets the user input the graph structure dynamically. This helps beginners experiment with different graphs and test their understanding.
def dfs_user_input(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs_user_input(graph, neighbor, visited)
graph = {}
edges = int(input("Enter the number of edges: "))
for _ in range(edges):
u, v = map(int, input("Enter an edge (u v): ").split())
graph.setdefault(u, []).append(v)
graph.setdefault(v, [])
start = int(input("Enter the starting node: "))
print("DFS traversal starting from node", start, ":")
dfs_user_input(graph, start)This program allows you to create a graph dynamically by entering the number of edges and node connections. You can then specify the starting node to begin the DFS traversal. This version helps learners understand how the DFS algorithm interacts with different types of input data and how graphs are built programmatically.
Frequently Asked Questions (FAQ)
Below are some common questions students often ask when learning Depth-First Search in Python.
Q1: What is Depth-First Search (DFS)?
Depth-First Search is a graph traversal algorithm that explores as deep as possible along each branch before backtracking to explore other branches.
Q2: Where is DFS used in real life?
DFS is used in pathfinding, maze solving, scheduling problems, detecting cycles, and analyzing networks such as social media connections or road maps.
Q3: What’s the difference between DFS and BFS?
DFS goes deep before exploring other branches, while BFS (Breadth-First Search) explores all nodes level by level before moving deeper.
Q4: Is DFS recursive or iterative?
It can be implemented both ways. Recursion is more natural and easier to understand, while iteration using a stack is more efficient for large graphs.
Q5: Can DFS detect cycles in a graph?
Yes. By checking if a node is revisited while still in the recursion stack, DFS can detect cycles in both directed and undirected graphs.
Conclusion
Depth-First Search (DFS) is one of the simplest yet most powerful algorithms in computer science. It helps programmers understand how to explore connected structures like graphs and trees efficiently. In this article, we explored multiple ways to implement DFS in Python — from recursive and iterative methods to matrix-based and user-input approaches.
Each method has its own advantages. Recursive DFS is clean and easy to understand, while iterative DFS provides better control. Using an adjacency matrix is great for dense graphs, and interactive programs make learning more engaging. The best way to master DFS is to practice — modify the programs, add more nodes, and visualize how the traversal works.
Keep exploring, and soon you’ll find that DFS is not just a search algorithm — it’s a gateway to understanding many complex algorithms that power modern computing.
