Implement BFS algorithm using python OOP

Graph representation
Spread the love

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.

Graph representation
Graph representation

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


Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.