Pythonista Moments: Breadth-First Search

In order to have an accurate binary tree, it must be searchable. We should be able to traverse the tree (graph) and get the values we need from each node. The Breadth-First Search (BFS) is an algorithm used for such a task. It is a recursive algorithm to search all the vertices of a tree. The purpose of the algorithm is to visit all the vertices while avoiding cycles. The algorithm uses a sort of “queue”. BFS starts from a node at the front of the queue and adds it to its “visited” list. Next, it creates a list of that node’s adjacent nodes. Any node not on its “visited” list is put at the back of the queue. It then goes to the front of the queue, visits that first node and repeats the process until the queue is empty.

Consider the following code. The graph is created first. This is the “tree” we will be traversing. Next, we create two lists. The first will store the visited nodes of the graph and the next will store the nodes yet to be visited in its own queue. Function declaration is the next step. This method will have the parameters of the tree itself, the visited nodes, and the current node being evaluated. And with this function, the visited and queued lists will be appended. The while loop will execute so the search continues visiting nodes to mark as visited or moved to the queue. Finally, the driver code executes on first node we wish to visit.

theTree = {
'5' : ['2','9'],
'2' : ['3', '7'],
'9' : ['6'],
'3' : [],
'7' : ['6'],
'6' : []
}
visited_nodes = []
nodes_in_queue = []
def Breadth_First_Search(visited_nodes, theTree, node):
  visited_nodes.append(node)
  nodes_in_queue.append(node)
 
  while nodes_in_queue:
  z = nodes_in_queue.pop(0)
  for adjacent_node in theTree[z]:
    if adjacent_node not in visited_nodes:
      visited_nodes.append(adjacent_node)
      nodes_in_queue.append(adjacent_node)
print('The order of the Breadth First Search is: ')
Breadth_First_Search(visited_nodes, theTree, '5')
print(f'\nThe list of visited nodes: {visited_nodes}. \nThe list of nodes left in the queue: {nodes_in_queue}')

And here is the Output:

The order of the Breadth First Search is: 
5 2 9 3 7 6
The list of visited nodes: ['5', '2', '9', '3', '7', '6'].
The list of nodes left in the queue: []

And there we have it, folks! The Breadth First Search Algorithm in action! If you enjoyed this brief tutorial, please follow me, Z. Myricks, for more guides in all things Python and Natural Language Processing. Make sure to follow Plain Simple Software for more software articles!