# 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**

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

**Disadvantages of BFS**

- The execution time of this algorithm is very slow because the time complexity of this algorithm is exponential.
- 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:

- Create a graph.
- Initialize a starting node.
- Send the graph and initial node as parameters to the bfs function.
- Mark the initial node as visited and push it into the queue.
- Explore the initial node and add its neighbours to the queue and remove the initial node from the queue.
- Check if the neighbours node of a neighbouring node is already visited.
- If not, visit the neighbouring node neighbours and mark them as visited.
- 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,

- How to implement Depth First Search algorithm in Python
- How to implement a Queue data structure in Python

## Leave a Reply

You must be logged in to post a comment.