Breadth First Search (BFS)

Traverse or search a graph or tree level by level.

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices at the current depth level before moving to the next level. It uses a queue data structure to manage the order of exploration, ensuring a level-by-level traversal.

BFS is commonly used for solving shortest path problems in unweighted graphs and finding connected components.

How the Algorithm Works

Here’s how BFS works:

  1. Start at the root node (or any arbitrary node for a graph).
  2. Enqueue the starting node and mark it as visited.
  3. While the queue is not empty:
    • Dequeue a node from the front of the queue.
    • Explore all its unvisited neighbors:
      • Mark each neighbor as visited and enqueue it.
  4. Repeat until all reachable nodes have been visited.

What makes BFS unique is its guarantee to explore the closest nodes first, making it ideal for finding the shortest path in unweighted graphs.

Time & Space Complexities

  • Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and edge is processed once.
  • Space Complexity: O(V), due to the storage required for the queue and the visited list.

When to Use

BFS is suitable for problems like:

  • Finding the shortest path in an unweighted graph.
  • Checking if a graph is bipartite.
  • Solving puzzles like the shortest path in a maze.
  • Performing level-order traversal in trees.

Code Examples

from collections import deque

def bfs(start, visited, adj):
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        for neighbor in adj[node]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# Example usage
vertices = 5
adj = [
    [1, 2],   # Neighbors of node 0
    [0, 3, 4],# Neighbors of node 1
    [0],      # Neighbors of node 2
    [1],      # Neighbors of node 3
    [1]       # Neighbors of node 4
]

visited = [False] * vertices
print("BFS Traversal: ", end="")
bfs(0, visited, adj)

Problems to Solve

WIP

Resources