Breadth-first search in a graph with python

In Implementing graph with python and how to traverse we learn how we can implement graph with python. In this article, we are going to talk about the breadth-first search and how we can achieve it using python. If you haven’t read about implementing a graph with python read it here. If you have read it lets see Breadth-first search in a graph with python

What is a breadth-first search?

Breadth-first search in simple words is traversing a level first before going deep into any branch of the graph. Let’s understand this with an example.

The breadth-first traversal of this graph is A B C E D F.

Start from A reach to B and C, from B reach to E and from C reach to D and the from E reach F

Thus we achieve the traversal as A B C E D F.

Let’s look a the code for this and try to implement a breadth-first search in a graph with python.

class Node:
        def __init__(self, data):
                self.data = data
                self.edge = []

        def add_edge(self,edge):
                self.edge.append(edge)

        def traverse(self):
                traversed = []
                queue = []
                for ed in self.edge:
                    queue.append(ed)
                print(self.data)
                traversed.append(self)
                while len(queue) != 0:
                        vertex = queue[0]
                        queue = queue[1:len(queue)]
                        if vertex not in traversed:
                            print(vertex.data)
                            traversed.append(vertex)
                            for ed in vertex.edge:
                                    queue.append(ed)



graphroot = Node('A')

# Lets add a new vertex

vert = Node('B')

# Lets connect the vertex.

vert.add_edge(graphroot)
graphroot.add_edge(vert)

# adding more vertices
vert2=Node('C')

vert2.add_edge(graphroot)
graphroot.add_edge(vert2)

vert3= Node('E')

vert2.add_edge(vert3)
vert3.add_edge(vert2)

vert4 = Node('D')

vert4.add_edge(vert2)
vert2.add_edge(vert4)

vert5 = Node("F")

vert5.add_edge(vert3)
vert3.add_edge(vert5)

graphroot.traverse()

Code walkthrough

Let’s see we created a node that has data and edges, every new node is attached using edges and data. Now if we look at BFS traversal code which is this part.

 def traverse(self):
                traversed = []
                queue = []
                for ed in self.edge:
                    queue.append(ed)
                print(self.data)
                traversed.append(self)
                while len(queue) != 0:
                        vertex = queue[0]
                        queue = queue[1:len(queue)]
                        if vertex not in traversed:
                            print(vertex.data)
                            traversed.append(vertex)
                            for ed in vertex.edge:
                                    queue.append(ed)

We have created 2 data structures traversed (to keep track of all the nodes visited to avoid cycles.), queue (to keep track of what to visit next). Now we start traversing using edges, every time we reach a vertex we put the connecting vertex in the queue., so that we can traverse it in the further iteration. Let’s have a look one by one.

Reach A
Traversed = [A]
Queue = [B, C]

Reach B after taking out the first element.
Traversed = [A,B]
Queue = [C, E]

Reach C
Traversed = [A,B,C]
Queue = [E,D]

Reach E
Traversed = [A,B,C,E]
Queue = [D,F]

Reach D
Traversed = [A,B,C,E,D]
Queue = [F]

Reach F
Travered = [A,B,C,E,D,F]
Queue = []

Traversal complete.

So this was the very basic flow of how the breadth-first traversal happens. We will be talking about depth-first traversal in our next articles.

If you like the articles please share and subscribe.

You can read about binary tree in python here.

If you like the article please share and subscribe. Follow us on facebook and install our android application.