Python’s Search Method Uses Breadth-First
When searching a tree or graph using Python, you can choose between using the breadth-first or depth-first 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 breadth-first search is in Python, how the breadth-first 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 breadth-first search and how it is used.
search.
What is Breadth-First Search?
As was discussed earlier, one approach for searching graphs or trees is referred to as Breadth-First Search (BFS). In order to fully explore the tree, you will need to stop at each node. Breadth-First 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 breadth-first 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 Breadth-First 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 breadth-first 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 breadth-first 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 Breadth-first 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 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
2
). Discovering Our Way to see if there is a route connecting two nodes, we can utilize either Breadth-First or Depth First Traversal.