How to implement Breadth First Search algorithm in Python

This Python tutorial helps you to understand what is the Breadth First Search algorithm and how Python implements BFS.

Algorithm for BFS

BFS is one of the traversing algorithm used in graphs. This algorithm is implemented using a queue data structure. In this algorithm, the main focus is on the vertices of the graph. Select a starting node or vertex at first, mark the starting node or vertex as visited and store it in a queue. Then visit the vertices or nodes which are adjacent to the starting node, mark them as visited and store these vertices or nodes in a queue. Repeat this process until all the nodes or vertices are completely visited.

 

Advantages of BFS

  1. It can be useful in order to find whether the graph has connected components or not.
  2. It always finds or returns the shortest path if there is more than one path between two vertices.

 

Disadvantages of BFS

  1. The execution time of this algorithm is very slow because the time complexity of this algorithm is exponential.
  2. This algorithm is not useful when large graphs are used.

 

Implementation of BFS in Python ( Breadth First Search )

Source Code: BFS in Python

graph = {'A': ['B', 'C', 'E'],
         'B': ['A','D', 'E'],
         'C': ['A', 'F', 'G'],
         'D': ['B'],
         'E': ['A', 'B','D'],
         'F': ['C'],
         'G': ['C']}
         
         
def bfs(graph, initial):
    
    visited = []
    
    queue = [initial]
 

    while queue:
        
        node = queue.pop(0)
        if node not in visited:
            
            visited.append(node)
            neighbours = graph[node]
 
            
            for neighbour in neighbours:
                queue.append(neighbour)
    return visited
 
print(bfs(graph,'A'))

Explanation:

  1. Create a graph.
  2. Initialize a starting node.
  3. Send the graph and initial node as parameters to the bfs function.
  4. Mark the initial node as visited and push it into the queue.
  5. Explore the initial node and add its neighbours to the queue and remove the initial node from the queue.
  6. Check if the neighbours node of a neighbouring node is already visited.
  7. If not, visit the neighbouring node neighbours and mark them as visited.
  8. Repeat this process until all the nodes in a graph are visited and the queue becomes empty.

Output:

['A', 'B', 'C', 'E', 'D', 'F', 'G']

 

You can also read,

 

Leave a Reply