Breadth First Traversal in Python

A graph is a non linear data structure. We often use graphs to represent different real world objects like maps and networks. In this article, we will study breadth first traversal to print all the vertices in a graph. We will also implement the breadth first traversal algorithm in Python.

What is breadth first traversal?

Breadth first traversal is a graph traversal algorithm to print all the vertices in a graph. In this algorithm, we start with a vertex and print its value. Then we print all the neighbors of the current vertex. After that, we select every neighbor of the current vertex and print all of its neighbors. This process continues until all of the vertices in the graph are printed.

Let us understand this process by performing a breadth first traversal on the following graph.

Suppose that we start from vertex A.

After printing vertex A, we will print all of its neighbor vertices i.e. B, D, E, and F.

After printing B,D, E, and F, we will select one of these vertices. Let us select D.

As D has no neighbor that needs to be printed, we will move back to A and choose another neighbor of A. Let us select E.

As E has no neighbor that needs to be printed, we will move back to A and choose another neighbor of A. Let us select F.

As F has no neighbor that needs to be printed, we will move back to A and choose another neighbor of A. Let us select B.

Now, we will print all the neighbors of B that have not been printed yet. Hence, we will print C. 

At this point, you can observe that all of the vertices in the graph have been printed in the order A, B, D, E, F, C . So, we will terminate the algorithm. 

Algorithm for breadth first traversal 

The algorithm for depth first traversal of a graph is implemented using a queue data structure. Here, we will assume that we have a connected graph. In other words, we can reach each vertex of the graph from the starting vertex.

We will maintain a queue to store the vertices that have not been printed and a list to store the visited vertices. After that we will process the graph using the following algorithm.

1. Create an empty queue Q to store the vertices that have not been printed.
2. Create an empty list L to store the visited vertices.
3. Insert source vertex into the Q and L.
4. If Q is empty, Go to 9. Else go to 5.
5. Take out a vertex v from Q.
6. Print the vertex v.
7. Insert all the neighbors of v that are not in L into Q as well as L.
8. Go to 4.
9. Stop.

This Algorithm can be demonstrated using the following source code for the graph given in the figure above.

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def BFS_Algorithm(input_graph, source):
    Q = Queue()
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        print("At:",vertex)
        print("Printing vertex:",vertex)
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                print("At vertex, adding {} to Q and visited_vertices".format(vertex, u))
                Q.put(u)
                visited_vertices.append(u)
        print("visited vertices are: ", visited_vertices)


print("BFS traversal of graph with source A is:")
BFS_Algorithm(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
BFS traversal of graph with source A is:
At: A
Printing vertex: A
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
At vertex, adding A to Q and visited_vertices
visited vertices are:  ['A', 'B', 'D', 'E', 'F']
At: B
Printing vertex: B
At vertex, adding B to Q and visited_vertices
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: D
Printing vertex: D
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: E
Printing vertex: E
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: F
Printing vertex: F
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']
At: C
Printing vertex: C
visited vertices are:  ['A', 'B', 'D', 'E', 'F', 'C']

In the output, you can observe that the vertices have been printed in the order A, B, D, E, F, and C.

Implementation of Breadth first traversal in Python

As we have discussed the general idea for breadth first traversal of a graph and observed how the algorithm works using the python program, we can implement the breadth first traversal algorithm as follows.

from queue import Queue

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def BFS(input_graph, source):
    Q = Queue()
    visited_vertices = list()
    Q.put(source)
    visited_vertices.append(source)
    while not Q.empty():
        vertex = Q.get()
        print(vertex, end= " ")
        for u in input_graph[vertex]:
            if u not in visited_vertices:
                Q.put(u)
                visited_vertices.append(u)


print("BFS traversal of graph with source A is:")
BFS(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
BFS traversal of graph with source A is:
A B D E F C 

Conclusion

In this article, we have discussed the breadth first traversal algorithm for a fully connected graph in python. To read more about other algorithms, you can read this article on In-order tree traversal in Python.