Python’s Search Method Uses BreadthFirst
When searching a tree or graph using Python, you can choose between using the breadthfirst or depthfirst search approach. These two concepts are among the most important areas of Python education for novice programmers to focus on. In this section, we will discuss what exactly breadthfirst search is in Python, how the breadthfirst search algorithm works, how to implement it in Python with an example code, and the results. In addition to this, we will discuss the practical applications of breadthfirst search and how it is used.
search.
What is BreadthFirst Search?
As was discussed earlier, one approach for searching graphs or trees is referred to as BreadthFirst Search (BFS). In order to fully explore the tree, you will need to stop at each node. BreadthFirst Search is a recursive method that can be used to search through all of the nodes that make up a tree or graph. In Python, the BFS operation can be carried out utilising data structures such as lists or tuples. The breadthfirst search operates almost exactly the same way in both trees and graphs. The only difference is that the tree might feature loops, which would make it possible for us to return to the same node multiple times.
node.
BFS Algorithm
Before we move on to learning how to develop Python code for it and discussing its results, let’s have a look at the methodology that BreadthFirst employs. As an illustration, think of the Rubik’s Cube. It is said that the Rubik’s Cube is searching for a solution that will allow it to transform from a jumble of colours into a single colour. When we compare the Rubik’s Cube to a tree or a graph, we may draw the conclusion that the Rubik’s Cube’s possible states correlate to the vertices of our network, and the Rubik’s Cube’s possible actions correlate to the graph’s edges. This allows us to say that the Rubik’s Cube can be solved in a total of 256 different ways.
The bfs algorithm is based on the steps that were explained earlier.
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.
Because breadthfirst search goes across each and every node of the provided graph, a typical BFS algorithm divides each node or vertex of the tree or graph into two separate parts.
groups.
 Visited
 Not visited
The purpose of the approach that has been discussed is to visit each vertex while avoiding recurrent cycles at the same time as doing so. BFS begins with a single node, then investigates all of the other nodes that are within one distance, then investigates all of the other nodes that are within two distances, and so on. BFS requires a queue in order to keep track of the nodes that still need to be visited. (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
First, we used the strategy known as breadthfirst search to construct the graph that was seen earlier using the Python programme. After that, we have started two lists: the first list is designed to record the nodes of the graph that the BFS algorithm has visited, and the second list is designed to record the nodes that are currently contained within the queue.
After completing the procedures outlined above, we have successfully declared a function that accepts as inputs visited nodes, the graph itself, and the node. Within a single function, we are required to continue adding items to the queue list and the visited_vertices list.
After that, the programme will execute the while loop on the queue of nodes that have not yet been visited. After that, it will erase and display the current node as it will appear after visiting all of the nodes in the queue. Finally, we have completed the process by utilising the for loop to search for unvisited nodes before adding them to the visited_vertices and queue lists respectively. After that, we used the parameter to make a call to the BFSearch function. This is the very first thing that we want to do in the
output.
Time Complexity
The time required to complete the Breadthfirst Search algorithm is O(V+E), where V is the number of vertices and E is the number of links in the network. In addition, the BFS algorithm utilises space that is O(V).
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 BreadthFirst. PeertoPeer (P2P) Networks BFS is often used to discover all neighbor vertices in peertopeer 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 BreadthFirst Search algorithm to hit all nodes in networking.
 In garbage assemblage, Cheney’s technique is used to duplicate trash compilation using BreadthFirst Search.
 Cycle identification in undirected networks can be accomplished via BreadthFirst Search or DFS (Depth First Search). Cycles in directed networks can also be found using BFS.

Algorithm FordFulkerson:
To determine the optimal stream in the FordFulkerson method, we can utilize either BreadthFirst or Depth First Traversal. It is preferable to use BreadthFirst Traversal since it decreases the worstcase time complexity to O (VE
^{ 2 }
). Discovering Our Way to see if there is a route connecting two nodes, we can utilize either BreadthFirst or Depth First Traversal.