4.2.3.1 Breadth-First Search (BFS)

(Difficulty Note: Analogies help here. The "layers" concept is important.)

Breadth-First Search (BFS) is like exploring a maze by finding everything that's one step away from you, then everything two steps away, then everything three steps away, and so on. It explores "layer by layer."

How it works (simplified):

Start at a specific point (node).
Visit all its direct neighbors (nodes one step away).
Then, visit all the neighbors of those neighbors (nodes two steps away), but make sure you haven't visited them already.
Keep expanding outwards, layer by layer, until you find what you're looking for or visit every reachable node.

Example: Imagine finding the closest friends of your friends on a social network. BFS would find all your direct friends first, then all their direct friends, and so on.

When is it used? BFS is great for finding the shortest path in terms of the number of steps (or connections) between two points, or for finding all reachable nodes in a network. It's used in social media (finding connections), network routing (finding the quickest path by hops), and web crawlers (indexing web pages).

Bibliography:

Breadth-First Search (BFS). (2025, March 4). GeeksforGeeks. Retrieved July 11, 2025, from https://www.geeksforgeeks.org/python/python-program-for-breadth-first-search-or-bfs-for-a-graph/
Breadth-first Search (BFS) Algorithm. (2024, December 22). Interview Kickstart. Retrieved July 11, 2025, from https://interviewkickstart.com/blogs/learn/breadth-first-search-algorithm

Further Reading:

What is Breadth First Search? (n.d.). Educative.io. Retrieved from https://how.dev/answers/what-is-breadth-first-search