Breadth First Search

In my previous post about Queues, I mentioned that they are the "best friend" of an algorithm called Breadth-First Search (BFS). If you’ve ever wondered how GPS finds the shortest route or how LinkedIn knows someone is a "2nd-degree connection," you’re looking at BFS in action.

What is BFS?

BFS is a way of "searching" through a tree or a graph. Unlike other methods that dive deep into one branch until they hit the bottom, BFS explores layer by layer.

Imagine you drop a pebble into a still pond. The ripples spread out in perfect circles, hitting everything nearby first, then moving to things further away. That is exactly how BFS works.

The "Layer" Logic

Think of it like searching for a specific book in a library:

 * Level 0: You start at your current shelf.

 * Level 1: You check all the shelves immediately next to you.

 * Level 2: You check the shelves next to those.

Because you check everything at Level 1 before moving to Level 2, BFS is guaranteed to find the shortest path in an unweighted graph.

Why the Queue is Essential

To keep track of who to visit next without getting lost, BFS uses a Queue (FIFO).

 * Visit the starting point and put its neighbors into the Queue.

 * Dequeue the first person/node in line.

 * Visit their neighbors and add them to the back of the Queue.

 * Repeat until the Queue is empty.

A Quick JavaScript Example

Here is how you might find if a "target" exists in a simple social network:

function bfs(graph, startNode, target) {

    let queue = [startNode];

    let visited = new Set(); // To avoid walking in circles!



    while (queue.length > 0) {

        let currentNode = queue.shift(); // First-In, First-Out



        if (currentNode === target) return "Found it!";



        if (!visited.has(currentNode)) {

            visited.add(currentNode);

            // Add all unvisited neighbors to the back of the line

            queue.push(...graph[currentNode]);

        }

    }

    return "Not found";

}

When to use BFS?

 * Shortest Path: Finding the minimum number of moves to solve a puzzle.

 * Social Networking: Finding "Friends of Friends."

 * Web Crawlers: Google uses similar logic to discover new pages by following links layer by layer.

BFS is all about patience. It doesn't rush deep into the unknown; it makes sure the immediate surroundings are safe and explored first!

Would you like me to create a visual comparison between BFS and DFS (Depth-First Search) for your next post?