Breadth-First Search (BFS) Explained

Breadth-First Search (BFS) is a fundamental graph traversal algorithm. It explores the graph level by level, starting from a given source node and expanding outwards to all its neighbours before moving on to the next level.

---

Example:

INPUT : [ [0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 1] ] , 2

OUTPUT: 2 -> 0 -> 1 -> 3

Key Concepts

• Graph Structure:
  BFS works on graphs (both directed and undirected) as well as trees.
• Level-Order Traversal:
  Nodes are visited in order of their distance from the starting node (i.e., by increasing number of edges).
• Queue Data Structure:
  BFS uses a FIFO (first-in, first-out) queue to keep track of nodes to visit next.

---

How BFS Works

1. Initialization:
   • Mark the starting node as visited.
   • Enqueue the starting node.
2. Iteration:
   • Dequeue a node from the front of the queue.
   • Process the current node (e.g., record its value).
   • For each unvisited neighbour of the current node:
     • Mark the neighbour as visited.
     • Enqueue the neighbour.
3. Termination:
   • Repeat the iteration until the queue is empty. At this point, all reachable nodes from the starting node have been visited.

---

Time and Space Complexity

Time Complexity: O(V + E)

• V = number of vertices
• E = number of edges
• Every vertex and edge is processed once.

Space Complexity: O(V)

• In the worst case, the queue holds all vertices in the graph.

---

Applications of BFS

• Shortest Path:
  BFS is ideal for finding the shortest path in unweighted graphs.
• Level Order Traversal:
  In trees, BFS performs a level order traversal.
• Connected Components:
  BFS can help determine the connected components in a graph.
• Web Crawlers:
  Used to explore the web layer by layer starting from a seed URL.