Depth First Search (DFS) and Breadth First Search (BFS) for Beginners (with python code)
Understanding Depth First Search (DFS) and Breadth First Search (BFS) is fundamental in computer science, especially in the context of graph traversal and pathfinding algorithms. Let's dive into these concepts in a structured manner.
1. Introduction
Depth First Search (DFS) and Breadth First Search (BFS) are two fundamental algorithms used to traverse or search through graphs and tree data structures.
These algorithms can be applied to a wide range of problems, such as pathfinding, cycle detection, and network analysis.
2. Depth First Search (DFS)
2.1. How DFS Works
DFS explores as far as possible along each branch before backtracking.
It uses a stack data structure to keep track of nodes to be visited.
2.2. Python Code for DFS
# Depth First Search in Python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
dfs(graph, 'A')
2.3. Usage of DFS
Pathfinding: Finding paths between nodes in a graph.
Cycle detection: Detecting cycles in a graph.
Topological sorting: Ordering of vertices in a Directed Acyclic Graph (DAG).
3. Breadth First Search (BFS)
3.1. How BFS Works
BFS explores all nodes at the present depth level before moving on to the nodes at the next depth level.
It uses a queue data structure to keep track of nodes to be visited.
3.2. Python Code for BFS
# Breadth First Search in Python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=' ')
visited.add(node)
queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
return visited
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
bfs(graph, 'A')
3.3. Usage of BFS
Shortest path: Finding the shortest path in an unweighted graph.
Level order traversal: Traversing nodes level by level.
Connected components: Identifying connected components in an undirected graph.
4. Stack and Queue in DFS and BFS
4.1. Stack in DFS
DFS uses a stack (either explicitly or via recursion) to keep track of the nodes to visit next.
Nodes are pushed onto the stack when they are discovered and popped when they are visited.
4.2. Queue in BFS
BFS uses a queue to keep track of the nodes to visit next.
Nodes are enqueued when they are discovered and dequeued when they are visited.
5. Differences and Nuances
5.1. Order of Traversal
DFS explores a path to its end before backtracking.
BFS explores all neighbors at the current depth before moving to nodes at the next depth level.
5.2. Data Structures Used
DFS uses a stack, which can be implemented using recursion.
BFS uses a queue.
5.3. Applications
DFS is more suitable for problems where we need to visit all paths from a node, such as in puzzles or maze solving.
BFS is better for finding the shortest path or exploring nodes level by level.
6. Explanation with diagrams
+----------------+
| Start at Node |
+----------------+
|
+---------+
| Push Node|
+---------+
|
+---------+
| Pop Node |
+---------+
|
+------------------+
| Visit and Process |
+------------------+
|
+-----------------------+
| Push Neighbors (if any)|
+-----------------------+
|
Repeat until stack is empty
+----------------+
| Start at Node |
+----------------+
|
+---------+
| Enqueue |
+---------+
|
+---------+
| Dequeue |
+---------+
|
+------------------+
| Visit and Process |
+------------------+
|
+-----------------------+
| Enqueue Neighbors (if any)|
+-----------------------+
|
Repeat until queue is emptyLet's use a simple tree for both Depth First Search (DFS) and Breadth First Search (BFS) to
illustrate their execution step by step with diagrams. We'll use the following binary tree
as our example:
A
/ \
B C
/ \ \
D E F
Depth First Search (DFS) with Stack
Start at Node A:
Stack: [A]
Visit A.
A
/ \
B C
/ \ \
D E F
Visit A, Push B and C:
Stack: [B, C]
Pop A.
A
/ \
B C
/ \ \
D E F
Visit B, Push D and E:
Stack: [C, D, E]
Pop B.
A
/ \
B C
/ \ \
D E F
Visit D:
Stack: [C, E]
Pop D.
A
/ \
B C
/ \ \
D E F
Visit E:
Stack: [C]
Pop E.
A
/ \
B C
/ \ \
D E F
Visit C, Push F:
Stack: [F]
Pop C.
A
/ \
B C
/ \ \
D E F
Visit F:
Stack: []
Pop F.
A
/ \
B C
/ \ \
D E F
Breadth First Search (BFS) with Queue
Start at Node A:
Queue: [A]
Visit A.
A
/ \
B C
/ \ \
D E F
Visit A, Enqueue B and C:
Queue: [B, C]
Dequeue A.
A
/ \
B C
/ \ \
D E F
Visit B, Enqueue D and E:
Queue: [C, D, E]
Dequeue B.
A
/ \
B C
/ \ \
D E F
Visit C, Enqueue F:
Queue: [D, E, F]
Dequeue C.
A
/ \
B C
/ \ \
D E F
Visit D:
Queue: [E, F]
Dequeue D.
A
/ \
B C
/ \ \
D E F
Visit E:
Queue: [F]
Dequeue E.
A
/ \
B C
/ \ \
D E F
Visit F:
Queue: []
Dequeue F.
A
/ \
B C
/ \ \
D E F
Support Our Efforts and Earn Together 🚀
Visit https://parucodes.github.io/ today and start your journey to becoming a fast, accurate, and confident touch typist.
If you find our website useful and want to support us, consider joining the exciting world of Bitcoin mining on your mobile phone. Follow this link: Mine PI Bitcoin and use my username prarthanadp as your invitation code. With the referral code prarthanadp, you'll receive a special referral bonus.
Thank you for your support! Let's grow and earn together! 🌟
Comments
Post a Comment