Breadth First Traversal

Introduction

This is the first article in the Graph Traversals – Online Classes.

Dear Readers, these set of posts under Graph Traversals will make more sense if you have read the Graph Theory. Here is a quick brush up for the same. However, if you are familiar with Graph Theory and have a basic knowledge of what graphs are and how they are stored, you can dive into the traversals.

Later in the series we will discover that the Graph Traversals are widely used in various application. Let me point out a couple of real world examples here:

  • How can we conduct matches between teams in a Cricket tournament such that all group 1 teams can play match with all other teams in remaining groups?
  • How can I sponsor my World Tour with minimum expenses?
  • How do networks like Facebook or LinkedIn suggest new connections? Can’t we get a better way of solving it?
  • How to make my web crawler not miss any web page and store them in relatively logical groups?.

Many such problems can be addressed when we have an insight of traversals, not just Graph Traversals but Tree Traversals will also be helpful.

Breadth First Traversal

The first type of graph traversal we would like to learn is the Breadth First Traversal, as this is the simplest of all.
The Idea
In this traversal, we maintain an invariant, such that at any time all the nodes at a lesser distance from the start node will be visited before the node at a greater distance from the start node. This means that it expands the frontier between the discovered and undiscovered vertices uniformly across the breadth of the frontier.

Here is an example of such a traversal.
Breadth First Traversal

Here if you notice, we can divide the whole graph into five layers/frontiers.

  • Frontier 1 : Color : Grey, Vertex Set : {1}
  • Frontier 2 : Color : Blue, Vertex Set : {2, 3}
  • Frontier 3 : Color : Pink, Vertex Set : {4, 5, 6}
  • Frontier 4 : Color : Green Vertex Set : {7, 8}
  • Frontier 5 : Color : Purple, Vertex Set : {9}

It means that none of the Frontier n vertices can be visited until all the vertices in frontier n-1 is visited.

Describing the Algorithm

Step 1: Visit the first vertex, you can choose any node as the first node. And add it into the a queue.
Step 2: Repeat the below steps till the queue is not empty.
Step 3: Remove the head of the queue and while staying at the vertex, visit all connected vertices and add them to the queue one by one (you can choose any order to visit all the connected vertices).
Step 4: When all the connected vertices are visited. Repeat Step 3.

Pseudo code

Explanation

Let us choose the start vertex as vertex 1. Mark it visited and add it to the queue.
Breadth First Traversal

Step 1

: Remove the head of the queue (Vertex 1) and find all its connected and undiscovered vertices (Vertex 2 and 3). Mark them visited and add them to the queue.
Now the Queue contains Vertex 2 and 3. Vertices 1, 2 and 3 are already visited.
Breadth First Traversal

Step 2

: Remove the head of the Queue (Vertex 2) and mark all its connected undiscovered vertices (Vertex 5 and 6) as visited and add them to the queue.
Now the Queue contains Vertex 3, 5 and 6. Vertices 1, 2, 3, 5 and 6 are already visited.
Breadth First Traversal

Step 3

: Remove the head of the Queue (Vertex 3) and mark all its connected undiscovered vertices (Vertex 4) as visited and add it to the queue.
Now the Queue contains Vertex 5, 6 and 4. Vertices 1, 2, 3, 5, 6 and 4 are already visited.
Breadth First Traversal

Step 4

: Remove the head of the Queue (Vertex 5) and mark all its connected undiscovered vertices (Vertex 7) as visited and add it to the queue.
Now the Queue contains Vertex 6, 4 and 7. Vertices 1, 2, 3, 5, 6, 4 and 7 are already visited.
Breadth First Traversal

Step 5

: Remove the head of the Queue (Vertex 6) and mark all its connected undiscovered vertices (Vertex 8) as visited and add it to the queue.
Now the Queue contains Vertex 4, 7 and 8. Vertices 1, 2, 3, 5, 6, 4, 7 and 8 are already visited.
Breadth First Traversal

Step 6

: Remove the head of the Queue (Vertex 4) and mark all its connected undiscovered vertices (NA) as visited and add it to the queue. There are no undiscovered vertex connected to Vertex 4.
Now the Queue contains Vertex 7 and 8. Vertices 1, 2, 3, 5, 6, 4, 7 and 8 are already visited.
Breadth First Traversal

Step 7

: Remove the head of the Queue (Vertex 7) and mark all its connected undiscovered vertices (Vertex 9) as visited and add it to the queue.
Now the Queue contains Vertex 8 and 9. Vertices 1, 2, 3, 5, 6, 4, 7, 8 and 9 are already visited.
Breadth First Traversal

Step 8

: Remove the head of the Queue (Vertex 8) and mark all its connected undiscovered vertices (NA) as visited and add it to the queue. There are no undiscovered vertex connected to Vertex 8.
Now the Queue contains Vertex 8. Vertices 1, 2, 3, 5, 6, 4, 7, 8 and 9 are already visited.
Breadth First Traversal

Step 9

: Remove the head of the Queue (Vertex 9) and mark all its connected undiscovered vertices (NA) as visited and add it to the queue. There are no undiscovered vertex connected to Vertex 9.
Now the Queue contains Vertex 8. Vertices 1, 2, 3, 5, 6, 4, 7, 8 and 9 are already visited.
Breadth First Traversal

Source Code – Breadth First Traversal

Download the complete source code from github

Analysis of the algorithm

The running time complexity will be O(|V| +|E|). The first loop runs till the Queue has some value. It will be a max of V times. The inner loop runs for K times where K is the size of the adjacency list of the vertex (or the number of edges connected to the vertex under process).

You can also understand it in a way that we need to traverse all the edges and vertices once for the BFS, so it has to be of the order |V| + |E| .

The auxiliary space required is for the tempQueue and the visited list which is equal to |V| + |V| means O(|V|).

Applications of Breadth First Traversal

  • This can also be used in finding out shortest paths between two nodes.
  • Another application can be serializing and de-serializing a tree data structure.
  • It can also be used in garbage collection in modern programming languages, which is done by traversing an object graph.
  • It can also be used to test if a graph is bipartite.

Don’t forget to subscribe to TechieMe to get updates on latest posts.