Python

BFS Python

Searching in the field of programming is mainly divided into two types, Depth-first search (DFS) and Breadth-first search (BFS). These are the algorithms of searching used to search or traverse in the graph.

Breadth-First search is the phenomenon of traversing every node of the graph or a tree, so each node is traversed by two parts. One is the ‘visited’ portion, and the other is the ‘non-visited’ part. This means that this search aims to reach every node of the graph.

BFS pseudocode and algorithm

  • The first step is to put any first source node in the queue from the back.
  • Create the visited list or array and then put the nodes in it.
  • Use a while loop to check that the queue is not empty, and then keep on removing items in the visited list.
  • All the removed items are marked as visited and now also remove the neighbors that are unvisited from the queue as well.

Applications of BFS

  • It is used for GPS navigation.
  • It is utilized for finding the path.
  • It is utilized to build the index by search index.
  • Implementation of BFS.

Example 1

We first introduce the graph; we want to have the values that are to be traversed. Each node further contains the values. For instance, here, the first number 5 will connect with the two nodes 3 and 7. Similarly, all other numbers are connected with other nodes to form a graph. After defining the graph, we will contain two array integer data types to store the numeric values of the graph that are to be visited. Whereas the other one includes those nodes that are next to those that are visited.

Visited = []
Queue = []

Both arrays are empty at the time of starting the breadth-first search. But gradually, these arrays contain the values of the nodes as we have described in the graph.

After introducing two arrays, we will define a function to access and search all the nodes line-wise. This function takes the values of the visited array, the graph and the third one is the node. Inside the function, we will add values in both the arrays, as described in the algorithm; first, the values are entered inside the ‘queue’; when it is visited, that particular node is then transferred to the visited queue. So, for now, this function will add the values in the arrays by using an append function for each array. This function contains the nodes as a parameter in it.

Visited.append (node)
Queue.append (node)

After that, we will now access and visit the nodes through an approach. This way of accessing the nodes is similar to accessing arrays because we always apply a loop to visit each index iteratively. In the case of bfs, we will use a while loop, and inside this while loop, a for loop is added to satisfy the condition used by the while loop.

This while loop will directly target the queue because the nodes will be added to the queue first and then to the visited array. So the values will be extracted through the pop() function and will be stored in respective variables.

M = queue. Pop(0)

This value will be displayed on the calling of the print function. Now when the values from the queue are extracted, this value will be used to locate its neighbors that are to be entered in the queue. So we will use for loop here to allocate each neighbor till the end of the graph. The condition applied here is that if the value is not in the visited array, it means it has not been accessed earlier, then the visited array will be added by these new values (neighbor) through the append function. And similarly, the queue will also get the new neighbors’ value.

Visited. Append (neighbor)

The function call is made along with the visited array, the whole graph, and the node as a parameter.

Bfs (visited, graph, ‘5’)

After using this code, you can see the relevant output through the resultant console by using the execution button at the top of the toolbar.

You can see that the whole path will be accessed through the nodes. One thing can be observed here: all these starting nodes are displayed only because each time before the print feature, these nodes are popped out from the queue.

Example 2

This example works on the same technique: searching inside the graph or a tree. But here, we have used the approach of OOP (object-oriented programming) in python by using the class system. So first, we will import some features from the collections library. These features include the “defaultdict” that contains the dictionary in Python language.

Moving towards the class, first, we define the class name, and inside the class, here is the constructor. As constructors are those features that are executed automatically as we create the object of the class. The object of the class is needed to access the class features. We will also create the object for the graph class later in the article. First, the constructor is defined here to initialize the list taken as a graph.

Defaultdict (list)

“Is” used to store the graph in the default dictionary.

After that, a function is used here, ‘added’ to add the new node or edge to the graph. The nodes are also known as edges and are represented by ‘u,.’ In contrast, the distance between the edges is represented by the vertex and is mentioned by ‘v.’ So inside the function, the graph will be entertained with new nodes through the append function.

Self.graph [u]. append (v)

Here we have also used a function to display the BFS of a graph. Initially, all the nodes are declared as they are not visited. In the first stage of searching, we will declare the status as FALSE.

Visited = [FALSE] * (max( self.graph) + 1)

Similarly, the queue is initialized as zero at the time of creation.

Queue = []

Let us now talk about the source node, which is the first one; we will enter it in the visited array and extract it from the queue as we did in the first example.

Queue.append(s)
Visited [s] = True

Now a while loop is used to dequeue all the nodes from the queue and then will print the value.

S = queue.pop (0)

After that, all the adjacent neighbor’s nodes will be extracted from the queue; if any node is already visited, then this will be entered in the visited queue. If-statement is used to check if the node is not visited already, then append it from the queue and enter it in the visited array.

G = graph() is somehow a way of the object creation of the constructor, and this object is further used to call the added function along with the neighbor values.

Conclusion

The article ‘BFS-Python’ contains a brief description of breadth-first search in the graph to traverse each node. This process of searching is done by having two lists that contain the visited and unvisited nodes in them. We have elaborated the concept by adding two elementary examples in the guide.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.