Introduction
Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental graph traversal algorithms. BFS explores all neighbor nodes at the current depth before moving to the next level, making it ideal for finding the shortest path. DFS, on the other hand, explores as far as possible along a branch before backtracking, making it suitable for topological sorting and solving mazes.
In this article, we will compare BFS and DFS in terms of approach, implementation, time complexity, and use cases.
What is Depth-First Search (DFS)?
Depth-First Search (DFS) is an algorithm that explores a graph or tree by moving as deep as possible before backtracking. It uses a stack(either explicit or recursive) to keep track of nodes.
How DFS Works
- Start from the root node or an initial node.
- Visit the node and mark it as visited.
- Explore its neighbors (children) one by one.
- Move to the next neighbor and repeat until no more nodes can be visited.
- If a dead end is reached, backtrack to the previous node.
Applications of DFS
- Solving mazes
- Finding connected components in networks
- Topological sorting
- Solving puzzles like Sudoku
Implementation of DFS in Python
Below is the Python implementation of DFS using recursion:
- Python
Python
def dfs(graph, node, visited=set()):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
# Example graph represented as an adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': [],
'E': [],
'F': [],
'G': []
}
print("DFS Traversal:")
dfs(graph, 'A')
Output:
DFS Traversal:
A B D E C F G
Explanation:
- The traversal starts at node 'A'.
- It moves to 'B', then 'D', and backtracks to 'E'.
- Then, it moves to 'C', explores 'F' and 'G'.
- DFS explores as deep as possible before backtracking.
246+ registered 
