Updated April 11, 2023
Definition of BFS Algorithm Python
BFS algorithm in python is used to traversing graphs or trees. Traversing a graph involves visiting each node. The full form of BFS is Breadth-First search, also known as Breadth-First Traversal algorithm. A recursive algorithm for searching all the vertices of a graph or tree is called Breadth-First Search. The depth-first search (DFS) algorithm is also used to search all the vertices of a graph or tree. Data structures such as a dictionary and lists can be used to build BFS in Python. The breadth-first search in a tree and a graph is nearly the same. The only difference is that the graph could have cycles, allowing us to return to the same node.
All nodes and vertices are visiting by the algorithm, So the time complexity of the BFS algorithm for the graph has an O(V + E), where V is the number of vertices of the graph and E is the number of edges of the graph.
The algorithm of the BFS algorithm:
The algorithm’s steps are as follows:
1. Put any of the vertices of the graph at the end of the queue to begin.
2. Take the first item in the queue and add it to the list of items that have been visited.
3. Make a list of the nodes that are adjacent to that vertex. Move individuals who aren’t on the visited list to the back of the queue.
4. Steps two and three should be repeated until the queue is empty.
A standard BFS method divides each vertex of the graph into two categories, as breadth-first search traverses each node of the graph.
1. Visited
2. Not visited
The algorithm’s goal is to visit every vertex while avoiding cycles. BFS begins with a node, then checks all nodes within one distance of the beginning node, then all nodes within two distances, and so on. BFS uses a queue (or list) to remember the nodes to be visited.
The pseudocode of the BFS algorithm –
In Python, the pseudocode for BFS is as follows:
create the queue que
label the vertex v as visited and place que
while que is not empty
remove the head vertex u of que
label and enqueue all unvisited neighbors of the vertex u
Working of the BFS algorithm in python
Let’s look at an example of how this BFS algorithm works. An undirected graph with 5 vertices is used in this example.
1. First, begin from vertex 4. Add it to the visited list, and all of its nearby vertices are added to the not visited list.
Visited list – [4] Queue – [3, 5, 1]
2. Next, visit the neighboring nodes of node 4 by visiting at the front of the queue.
Visited list – [4, 3] Queue – [5, 1]
3. Next, visit the neighboring nodes of node 3 by visiting at the front of the queue that is node 5. Because vertex 5 has an unvisited adjacent vertex 2, we tend to move it to the back of the queue.
Visited list – [4, 3, 5] Queue – [1, 2]
4. Next, visit node 1, which is at the front of the queue.
Visited list – [4, 3, 5, 1] Queue – [2]
5. Finally, only node 2 remains in the queue; visit node 2, and the queue becomes empty.
Visited list – [4, 3, 5, 1, 2] Queue – [ ]
Examples
Example for BFS algorithm in python to travels all the tree nodes –
Code:
#function implementing BFS algorithm
def bfs_algorithm( visited, graph, node ):
visited.append( node )
q.append( node )
# using loop to visit each node of the tree
while q:
v = q.pop( 0 )
print ( v, end = " " )
# visit neighbour
for u in graph[v]:
if u not in visited:
visited.append( u )
q.append( u )
# Driver Code
print( "Following is the result of the Breadth-First Search, starting from vertex 1:" )
# createing a grapgh
g = {
'1' : ( '2', '3' ),
'2' : ( '4', '5' ),
'3' : ( '6' ),
'4' : ( ),
'5' : ( '6' ),
'6' : ( )
}
# creating list to store visited nodes
visited = [ ]
# createing a queue
q = [ ]
# calling function
bfs_algorithm( visited, g, '1' ) Output:
As in the above program, the graph is created using the dictionary where keys are the node and values are its neighboring nodes that are mentioned by using the tuples. Next, the bfs_algorithm() function is defined, which accepts the visited list, graph, and node from where the traveling will starts. Inside the function, append the passed node to the visited list and queue and next used the while loop to visit each node and its neighbor of the tree and print them. Next, call the bfs_algorithm() function with created graph, visited list, and stating node, as we can see in the above output.
Conclusion
The BFS algorithm is also known as the Breadth-First Traversal algorithm. The BFS algorithm is used to traversing graphs or trees. Data structures such as a dictionary and list can be used to build BFS in Python. The time complexity of the BFS algorithm for the graph has an O(V + E).
Recommended Articles
We hope that this EDUCBA information on “BFS Algorithm Python” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
