BFS (Breadth-First Traversal) is the graph traversal algorithm. In this tutorial, I will show you how to implement a BFS algorithm using python OOP. To jump this tutorial, first, you have to know how to input a graph using python. If you don’t know then you can read this blog where I explained the input graphs in python.

###### Prerequisite : Graph representation in python on Adjacency list

Well, I assumed that you are familiar with how to input graphs in an adjacency list using python. Follow this code of graph. I will not explain to you these pieces of code because already I explain them in my blog.

## Input Graph using adjancy list

```
class Graph:
def __init__(self, nodes, is_directed=False):
self.is_directed = is_directed
self.nodes = nodes
self.adj_list = {}
for node in self.nodes:
self.adj_list[node] = []
def print_adj_list(self):
for node in self.nodes:
print("{} -> {}".format(node, self.adj_list[node]))
def add_edge(self, u, v):
self.adj_list[u].append(v)
if not self.is_directed:
self.adj_list[v].append(u)
def add_multiple_edges(self, edges):
for u, v in edges:
self.add_edge(u, v)
```

Well, Now see this graph. We are going to traverse this graph using the **BFS** algorithm.

Well, in this graph we can see the eight vertices or nodes and nine edges. First, you have to make two lists and store the nodes and edges.

```
nodes = ["A", "B", "C", "D", "E","G","H"]
edges = [
("A", "B"),
("B", "C"),
("A", "D"),
("D", "E"),
("D", "F"),
("E", "F"),
("E", "G"),
("F", "H"),
("G", "H")
]
```

Well, now define a new class whose name is **BFS** which extends the **Graph** class that I defined before. Let’s see the code I will explain you later.

```
from queue import Queue
class BFS(Graph):
def __init__(self, nodes, edges, is_directed=False):
super().__init__(nodes, is_directed)
self.add_multiple_edges(edges)
self.visited = {}
self.level = {}
self.parent = {}
self.output = []
self.queue = Queue()
# initail Task
for node in self.adj_list.keys():
self.visited[node] = False
self.parent[node] = None
self.level[node] = -1
```

Well, inside this class you can see a constructor or init method. This init method takes two parameters that are nodes and edges. This init method is also called the super method that means it sends data in the super class. Well, after I call a method which defined in the base class. This method generates an adjacency list for this graph. After then take a couple of lists and dictionaries as well as you have to import the Queue module.

Well, after then execute a loop to do the initial task. Inside the loop, I assign **False** and **None** in all dictionaries which I defined before.

## Algorithm for BFS

**Step 1:**SET STATUS = 1 (ready state)

for each node in G**Step 2:**Enqueue the starting node A

and set its STATUS = 2

(waiting state)**Step 3:**Repeat Steps 4 and 5 until

QUEUE is empty**Step 4:**Dequeue a node N. Process it

and set its STATUS = 3

(processed state).**Step 5:**Enqueue all the neighbours of

N that are in the ready state

(whose STATUS = 1) and set

their STATUS = 2

(waiting state)

[END OF LOOP]**Step 6:**EXIT

## BFS traversal Algorithm

Let’s see this code for BFS traversal.

```
def bfs_traversal(self, source):
# initial task
self.visited[source] = True
self.level[source] = 0
self.queue.put(source)
while not self.queue.empty():
u = self.queue.get()
self.output.append(u)
for v in self.adj_list[u]:
if not self.visited[v]:
self.visited[v] = True
self.parent[v] = u
self.level[v] = self.level[u] + 1
self.queue.put(v)
return self.output
```

Well, now I am going to explain this function. This function takes a perimeter which is the source node of our graph. Then assign visited source node is equal to True and level of the source node is equal to zero and push source node in the queue.

Well, now execute a loop until the queue is empty. Inside the loop, first, you have to pop the queue value then put it in the output list. Now you have to visit all nodes of the current working value’s unvisited nodes/vertices.

## Print destination node path from source

```
def print_path(self, destination):
path = []
while destination is not None:
path.append(destination)
destination = self.parent[destination]
path.reverse()
return path
```

Well, In this function you have to send a destination node. First, take an empty list to store the path. After then execute a loop until the destination is not **None**. Inside the loop, append the destination node in the path list. Then re-assign the destination node with the parent destination value. Finally, reverse the list and return it.

Well, now create an object then check all functions.

```
bfs = BFS(nodes, edges)
source = input("Enter Source : ")
print(bfs.bfs_traversal(source))
destination = input("Enter Destination : ")
print(bfs.print_path(destination))
```

The time complexity of BFS is O**(v+e).**

### Full Code of bfs algorithm in python:

```
from queue import Queue
class Graph:
def __init__(self, nodes, is_directed=False):
self.is_directed = is_directed
self.nodes = nodes
self.adj_list = {}
for node in self.nodes:
self.adj_list[node] = []
def print_adj_list(self):
for node in self.nodes:
print("{} -> {}".format(node, self.adj_list[node]))
def add_edge(self, u, v):
self.adj_list[u].append(v)
if not self.is_directed:
self.adj_list[v].append(u)
def add_multiple_edges(self, edges):
for u, v in edges:
self.add_edge(u, v)
class BFS(Graph):
def __init__(self, nodes, edges, is_directed=False):
super().__init__(nodes, is_directed)
self.add_multiple_edges(edges)
self.visited = {}
self.level = {}
self.parent = {}
self.output = []
self.queue = Queue()
# initail Task
for node in self.adj_list.keys():
self.visited[node] = False
self.parent[node] = None
self.level[node] = -1
def bfs_traversal(self, source):
self.visited[source] = True
self.level[source] = 0
self.queue.put(source)
while not self.queue.empty():
u = self.queue.get()
self.output.append(u)
for v in self.adj_list[u]:
if not self.visited[v]:
self.visited[v] = True
self.parent[v] = u
self.level[v] = self.level[u] + 1
self.queue.put(v)
return self.output
def level_of_node(self, node):
return self.level[node]
def print_path(self, destination):
path = []
while destination is not None:
path.append(destination)
destination = self.parent[destination]
path.reverse()
return path
nodes = ["1", "2", "3", "4", "5"]
edges = [
("1", "3"),
("1", "2"),
("1", "4"),
("2", "3"),
("2", "5"),
("3", "4"),
("3", "5"),
("4", "5"),
]
bfs = BFS(nodes, edges)
source = input("Enter Source : ")
print(bfs.bfs_traversal(source))
destination = input("Enter Destination : ")
print(bfs.print_path(destination))
print(bfs.level_of_node(destination))
// Output
Enter Source : 1
['1', '3', '2', '4', '5']
Enter Destination : 5
['1', '3', '5']
```