# Implement BFS algorithm using python OOP 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

for node in self.nodes:

for node in self.nodes:

if not self.is_directed:

for u, v in edges:

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.visited = {}
self.level = {}
self.parent = {}
self.output = []
self.queue = Queue()

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):
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)
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 Codeof 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

for node in self.nodes:

for node in self.nodes:

if not self.is_directed:

for u, v in edges:

class BFS(Graph):
def __init__(self, nodes, edges, is_directed=False):
super().__init__(nodes, is_directed)
self.visited = {}
self.level = {}
self.parent = {}
self.output = []
self.queue = Queue()

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)
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']`````` 