This week I decided to focus on Breadth First Search (BFS). It’s a topic that I personally haven’t looked at in a while, so it seemed like it would be a great refresher to review it.

I found this very helpful guide on stackabuse.com. According to stackabuse.com’s guide, BFS is an algorithm for traversing a graph level by level and the algorithm will visit all of the neighbors of the root node on the first level, then visit the child nodes on the second level, and so on.

Stackabuse.com has a helpful BFS visualization here:

https://s3.stackabuse.com/media/articles/bfs-gif.gif

Essentially, BFS involves exploring horizontal rows of nodes of a graph or tree structure, row by row.

Let’s review Queue structures in Python, as the guide states that BFS is typically implemented using a Queue structure to keep track of visited/un-visited nodes, so maybe we can understand the reasoning behind that.

According to guru99.com, a queue is a type of data structure that has a ‘First in First Out’ flow, whereby, the queue has data elements inserted at the back and are removed from the front. The author compares it to people waiting in line at a ticket counter, but I think it could also be compared to the conveyer belt at a grocery store where you might put your items, which would be removed one by one.

Steve Campbell from guru99.com demonstrates how to use a queue in python by using the queue library. According to Steve, you can simply import queue, and create a queue, like so:

import queue
q1 = queue.Queue()

Source: https://www.guru99.com/python-queue-example.html

The queue library seems to trivialize a lot of the work to create and use a queue structure in Python, because Steve Campbell goes on to include some various built-in methods inside the queue library which can be used to perform different actions:

put(item): This will put the item inside the queue.
get(): This will return you an item from the queue.
empty(): It will return true if the queue is empty and false if items are present.
qsize(): returns the size of the queue.
full(): returns true if the queue is full, otherwise false.
Source: https://www.guru99.com/python-queue-example.html

Because we need to keep track of visited and unvisited nodes through BFS, I think it makes sense that these resources would suggest using a queue, and I found another resource that explains the use of a queue with BFS with a lot of helpful detail: https://www.pythonpool.com/bfs-python/

According to pythonpool.com, we traverse with BFS starting at the source vertex, starting with k edges away, before visting any vertex k+1 edges away, and so on, until all vertices are visited that are reachable from the source vertex.

Pythonpool.com explains that there are three rules for traversing with BFS:

"Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
Rule 2 − If no adjacent vertex is found, then remove the first vertex from the queue.
Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty."
Source: https://www.pythonpool.com/bfs-python/

I think I have to spend a lot more time looking at this example and learning the ins and outs of BFS before I can attempt a leetcode problem, and that’s a bit more time than what I have to write a blog post by my deadline, but as a learning exercise, I’d like to take their code example with BFS, and translate it into psuedocode to help me understand it. I think that will be helpful for me for future learning and practice.

Here is the BFS example from pythonpool.com, implemented in python:

graph = {
    'A': ['B', 'C', "D"],
    'B': ['E', "F"],
    'C': ['G', "I"],
    'D': ["I"],
    'E': [],
    "F": [],
    'G': [],
    "I": []
}

def bfs(visit_complete, graph, current_node):
    visit_complete.append(current_node)
    queue = []
    queue.append(current_node)
 
    while queue:
        s = queue.pop(0)
        print(s)
 
        for neighbour in graph[s]:
            if neighbour not in visit_complete:
                visit_complete.append(neighbour)
                queue.append(neighbour)
 
bfs([], graph, 'A')
Source: https://www.pythonpool.com/bfs-python/

Taking a look at their implementation, it looks like they created a dictionary to represent their example graph, where the parent nodes are the keys, and the child nodes are the values. The way they implemented this, their function takes in a visited_complete list, which keeps track of the visited nodes, as well as the dictionary graph, and a current node. In their case, they call the function with an empty list, the dictionary graph, and the current node starting at the source vertex or root of the graph. So they have another empty list inside the function which they called queue to represent their queue, and they append the source vertex to it. They add the root of the graph to the queue, and mark it visited. While the queue is not empty, they pop the first node. Then they look for all of the neighboring nodes of the current node, and if they haven’t already been visited, they append the neighbor nodes to visited and mark them as visited. Then they append the neighboring nodes to the queue.

Sources:

Campbell, Steve. “Python Queue: FIFO, Lifo Example.” Guru99, 10 Sept. 2022, https://www.guru99.com/python-queue-example.html. Accessed 10 Nov. 2022.

Daripa, Sagarika. “How to Implement Breadth-First Search (BFS) Using Python.” Python Pool, 31 May 2021, https://www.pythonpool.com/bfs-python/. Accessed 10 Nov. 2022.

“Graphs in Python – Theory and Implementation.” Stack Abuse, https://stackabuse.com/courses/graphs-in-python-theory-and-implementation/lessons/breadth-first-search-bfs-algorithm/. Accessed 10 Nov. 2022.