Breadth-First Search in Python

In Python, the breadth-first and depth-first search techniques are implemented to search a tree or graph. These two are among the most crucial topics for every new Python coder to master. We'll look at what exactly breadth-first search is in Python, how its algorithm works, how to implement it in Python with an example code, and the results. We'll also learn about bfs' real-world applications and usage of breadth-first search.

What is Breadth-First Search?

Breadth-First Search (BFS) is a method for searching graphs or trees, as previously mentioned. Traversing the tree entails visiting every node. Breadth-First Search is a recursive method for searching all the nodes of a tree or graph. In Python, We can utilize data structures like lists or tuples to perform BFS. In trees and graphs, the breadth-first search is virtually identical. The only distinction is that the tree might have loops, which would enable us to revisit the same node.

BFS Algorithm

Let's look over the methodology Breadth-First uses prior to learning to write a Python code for it and discuss its output. Consider Rubik's Cube as an analogy. The Rubik's Cube is thought to be looking for a way to turn it from a jumble of hues into a single color. When comparing the Rubik's Cube to a tree or a graph, we can conclude that the cube's potential states correlate to the vertices of our network, and the cube's potential actions correlate to the graph's edges.

The bfs algorithm follows the steps discussed below.

To begin, place any one of the vertices of our graph at the lower extreme of the queue.
Add the very first element in the created queue to the list of objects that have already been checked out.
Create a list of all the nodes that seem to be near that vertex. Individual nodes which are not in the visited list should be moved to the rear of the queue.
Repeat the above two steps, i.e., steps 2 and 3, till our queue is reduced to 0.

As breadth-first search scans every node of the given graph, a standard BFS algorithm splits each node or vertex of the tree or graph into two distinct groups.

Visited
Not visited

The objective of the technique discussed is to visit each vertex while at the same time avoiding recurring cycles. BFS starts with a single node, then examines all nodes inside one distance, then all the other nodes under two distances, and so forth. To retain the nodes that remained to visit, BFS requires a queue (or, in Python, a list).

Code

# Python code to give the traversed path by BFS algorithm as output. BFS(int n) scans through the vertices which are reachable from n.
from collections import defaultdict as dd

class Graph:
  
    # Constructing a list
    def __init__(self):
  
        # default dictionary to store graph
        self.graph = dd(list)
  
    # defining function which will add edge to the graph
    def addEdgetoGraph(self, x, y):
        self.graph[x].append(y)
  
    # defining function to print BFS traverse
    def BFSearch(self, n):
  
        # Initially marking all vertices as not visited
        visited_vertices = ( len(self.graph ))*[False]
  
        # creating a queue for visited vertices
        queue = []
  
        # setting source node as visited and adding it to the queue
        visited_vertices[n] = True
        queue.append(n)
        
  
        while queue:
  
            # popping the element from the queue which is printed
            n = queue.pop(0)
            print (n, end = " ")
  
            # getting vertices adjacent to the vertex n which is dequed. 
            for v in self.graph[ n ]:
                if visited_vertices[v] == False:
                    queue.append(v)
                    visited_vertices[v] = True
  

# Example code
# Initializing a graph
graph = Graph()
graph.addEdgetoGraph(0, 1)
graph.addEdgetoGraph(1, 1)
graph.addEdgetoGraph(2, 2)
graph.addEdgetoGraph(3, 1)
graph.addEdgetoGraph(4, 3)
graph.addEdgetoGraph(5, 4)
  
print ( " The Breadth First Search Traversal for The Graph is as Follows: " )
graph.BFSearch(3)

Output:

The Breadth First Search Traversal for The Graph is as Follows: 
3 1

We have first generated the graph in the Python program shown above, for which we have applied the breadth-first search approach. After that, we have initialized two lists: one is to keep track of the nodes of the graph the BFS algorithm has visited, and another is to keep track of the nodes inside the queue.

We have declared a function with parameters visited nodes, the graph itself, and the node following the above steps. We have to keep adding the visited_vertices and queue lists within a function.

Then the program will execute the while loop on the queue of nodes yet to visit and then erase and display the current node as it has visited. Finally, we have used the for loop to look for unvisited nodes before appending them to the visited_vertices and queue lists. We then called the BFSearch function with the argument, which is the very first we want in the output.

Time Complexity

The Breadth-first Search algorithm has a temporal complexity of O(V+E), wherein V represents the number of vertices and E represents the number of links. Furthermore, the BFS algorithm has O(V) space complexity.

Applications of Breadth First Traversal

Shortest Path & Minimum Ranging: Tree for Unweighted Graph The least one in an unweighted graph is the route with the fewest edges. We usually reach a node from a source node using the fewest amounts of edges when utilizing Breadth-First. Peer-to-Peer (P2P) Networks BFS is often used to discover all neighbor vertices in peer-to-peer networking like BitTorrent.
Crawlers in Search Engines: Crawlers create indexes by going from breadth to depth. The goal is to start at the root page and explore all of the links from there.
Websites for Social Networking: We can use Breadth First Search to identify persons within a particular length 'm' from a member in social connections up to 'm' levels.
All nearby sites are found using Breadth First Search in GPS navigation devices.
A broadcasted packet uses the Breadth-First Search algorithm to hit all nodes in networking.
In garbage assemblage, Cheney's technique is used to duplicate trash compilation using Breadth-First Search.
Cycle identification in undirected networks can be accomplished via Breadth-First Search or DFS (Depth First Search). Cycles in directed networks can also be found using BFS.
Algorithm Ford-Fulkerson: To determine the optimal stream in the Ford-Fulkerson method, we can utilize either Breadth-First or Depth First Traversal. It is preferable to use Breadth-First Traversal since it decreases the worst-case time complexity to O (VE²). Discovering Our Way to see if there is a route connecting two nodes, we can utilize either Breadth-First or Depth First Traversal.

Next TopicPython Graphviz: DOT Language

← prev next →