Breadth-Frist Search (BFS) vs Depth-First Search (DFS)

 

When exploring all nodes in a graph, we have two fundamental traversal methods:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Breadth-Frist Search (BFS)

Key Idea

BFS explores nodes level by level, meaning it visits all neighbors of a node before moving deeper. This ensures that nodes are processed in increasing order of distance from the starting node.

Steps:

1. Start from a given node.
2. Visit all its unvisited neighbors.
3. Treat these neighbors as new starting points and visit their neighbors.
4. Repeat until all reachable nodes have been visited.

Code Implementation

Since BFS processes nodes in a First-In-First-Out (FIFO) order, a queue is the ideal data structure for implementation.

from collections import deque

# Graph representation (adjacency list)
neighbors = [
    [],  # 0 (not used)
    [3, 5, 7],  # 1
    [4, 7],  # 2
    [1, 6, 8],  # 3
    [2, 7, 9],  # 4
    [1],  # 5
    [3],  # 6
    [1, 2, 4],  # 7
    [3, 9],  # 8
    [4, 8]  # 9
]

v = 9
visited = [False] * (v + 1)
result = []

queue = deque([1])  # Start from node 1
while queue:
    current_node = queue.popleft()
    
    if not visited[current_node]:
        visited[current_node] = True
        result.append(current_node)
        
        for neighbor in neighbors[current_node]:
            if not visited[neighbor]:
                queue.append(neighbor)

print(result)

Depth-First Search (DFS)

Key Idea

DFS explores as deep as possible along one branch before backtracking. This method is useful for exploring all paths before moving wider.

Steps:

1. Start from a given node.
2. Visit its first unvisited neighbor.
3. Recursively continue this process until reaching a node with no unvisited neighbors.
4. Backtrack and visit the next unvisited neighbor.
5. Repeat until all nodes have been visited.

Code Implementation

Since DFS follows a Last-In-First-Out (LIFO) order, a stack is the ideal data structure for implementation.

# Graph representation (adjacency list)
neighbors = [
    [],  # 0 (not used)
    [3, 5, 7],  # 1
    [4, 7],  # 2
    [1, 6, 8],  # 3
    [2, 7, 9],  # 4
    [1],  # 5
    [3],  # 6
    [1, 2, 4],  # 7
    [3, 9],  # 8
    [4, 8]  # 9
]

v = 9
visited = [False] * (v + 1)
result = []

stack = [1]  # Start from node 1
while stack:
    current_node = stack.pop()
    
    if not visited[current_node]:
        visited[current_node] = True
        result.append(current_node)
        
        for neighbor in reversed(neighbors[current_node]): # Reverse neighbors to maintain order consistency
            if not visited[neighbor]:
                stack.append(neighbor)

print(result)