Write a Program to traverse a graph using breadth first search in python.
When it comes to graph algorithms one of the most fundamental one is the Breadth-First Search algorithm (BFS). The BFS algorithm is a simple yet powerful algorithm that can be used to traverse a graph or tree. It is a graph traversal technique that explores the nodes of a graph layer by layer, starting from the source node and moving toward its neighbors. In this blog post we will discuss what BFS is how it work and how it can be implemented in Python.
Program to Traverse a graph using the depth first search in Python
What is Breadth-First Search in Python?
BFS is a graph traversal algorithm that explores all the vertices of a graph or tree in breadth-first order i.e., it visits all the nodes at the same level before moving to the next level. BFS starts at the root (or the source node) and explores all the nodes at the current level before moving on to the next level. In other words BFS visits all the nodes that are at a distance of 1 from the source node then visits all the nodes at a distance of 2 and so on until all the nodes have been visited.
How does Breadth First Search in Python work?
The BFS algorithm starts at the source node and visits all the nodes at the current level before moving to the next level. The algorithm uses a queue data structure to store the nodes that are yet to be visited. The source node is added to the queue and its adjacent nodes are added to the queue. Then the node at the front of the queue is removed and visited. The adjacent nodes of the visited node that have not been visited yet are added to the queue. This process continues until the queue is empty i.e., all the nodes have been visited.
Implementation of Breadth First Search in Python
Now that we have discussed what BFS is and how it works let us see how we can implement in Python. We will implement BFS using adjacency list representation of the graph. The adjacency list is data structure that stores the edges of graph.
Here is the Python code to implement BFS
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
In above code we first import the deque data structure from the collections module. We then define the bfs function that takes two arguments the graph and the start node.
The visited set is used to keep track of the nodes that have been visited. We initialize the visited set to an empty set. The queue is used to store the nodes that are yet to be visited. We initialize the queue with the start node.
We then start a loop that runs until the queue is empty. In each iteration of the loop we remove the node at the front of the queue using the popleft method. If the node has not been visited yet we add it to the visited set and add its adjacent nodes to the queue.
We then return visited set which contains all the nodes visited by the BFS algorithm.
4 Ways to Implement Linear Search in Python – Linear Search in Python