Breadth-First Search

So, what's the meaning of a graph?

• A way to connect things to each other.

As an example: Let's think about a farm owner who has mangos that need to be sold. He searched among his friends and found that no one wants to buy mangos, so he now needs to search among his friends' friends.

The graph might look like this:

    You
   / | \
Alice Bob Claire
  |   |    | \
Peggy Anuj Thom Jonny

Now, is there a mango buyer? If yes, what's the shortest path to them? This is what BFS (Breadth-First Search) is always asking.

To search in the graph with BFS, you need to respect the order people are added in, so we use a common data structure for this mission called a queue, which works in the FIFO (First In, First Out) method.

Implementing the Graph

We will use hash tables to make a graph:

graph = {}
graph["you"] = ["alice", "bob", "claire"]

That's what we all need in Python for now.

How Our Algorithm Works

1. Initialize the queue with the starting node.
2. Pop a node from the queue.
3. Check if this node is the target node.
4. If yes, the search is successful.
5. If no, add all its neighbors to the queue.
6. Repeat until the queue is empty or the target is found.

If the queue was empty at the end, it means there's no mango seller in our graph.

Example in Python

from collections import deque
 
# Example graph
graph = {
    "you": ["alice", "bob", "claire"],
    "alice": ["peggy"],
    "bob": ["anuj", "peggy"],
    "claire": ["thom", "jonny"],
    "anuj": [],
    "peggy": [],
    "thom": [],
    "jonny": []
}
 
# Example is_seller function
def is_seller(name):
    return name.endswith('m')  # Example condition: name ends with 'm'
 
def search(name):
    # Initialize queue
    search_queue = deque()
    search_queue += graph[name]
 
    # Keep track of people already searched
    searched = []
 
    # BFS
    while search_queue:
        person = search_queue.popleft()  # Pop the first item (like JS shift)
        if person not in searched:
            if is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False
 
# Start the search
search("you")

Let's Make It Easier to Understand

1. Graph Setup: The graph dictionary represents connections between people.
2. Seller Check: The is_seller function checks if a name ends with 'm'.
3. Search Function: The search function:
   • Initializes a queue with the starting person's connections.
   • Uses a list to keep track of already checked people.
   • Uses a loop to go through each person in the queue:
     • If the person is a seller, it prints a message and returns True.
     • If not, it adds the person's connections to the queue and marks the person as searched.
4. Start Searching: Calling search("you") to begin the search from "you".

Conclusion

In this article, we've learned how to use the Breadth-First Search (BFS) algorithm to search through a network of connections. By using a queue, BFS checks each person step by step and avoids checking the same person twice, making it a quick way to find our target, like a "mango seller." This method is useful in many real-life situations, like finding friends on social networks or exploring web links.

This summary is based on Chapter Six of "Grokking Algorithms" by Aditya Bhargava, a great book that explains important algorithms with easy-to-understand pictures and examples.