Back to course

Lesson 39: Breadth First Search (BFS): Concept and Implementation

Algorithms: From Zero to Hero (A Beginner's Guide)

39. Breadth First Search (BFS)

BFS is a graph traversal algorithm that explores all the neighbor nodes at the current depth level before moving on to the nodes at the next depth level.

Concept: Exploring Layers

Imagine ripples in a pond. BFS explores layer by layer, finding all nodes one step away, then all nodes two steps away, and so on.

BFS uses a Queue to keep track of nodes to visit next, ensuring a level-by-level exploration.

Algorithm Steps

  1. Start at source node S, mark as visited, and enqueue it.
  2. While the queue is not empty:
    • Dequeue a node U.
    • For every unvisited neighbor V of U:
      • Mark V as visited and enqueue V.

Use Cases

  • Finding the shortest path in an unweighted graph (since it explores closest nodes first).
  • Web crawlers (crawling level by level).