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.

  • هنگامه

    Thank you for this great article. When I copy and paste the code into Eclips, it get error and it needs a class for "List". Where can I find that?

    • Yes, this happens because I intentionally skipped the imports. The following four imports needs to be added in your code.
      <pre brush="java">
      import java.util.ArrayDeque;
      import java.util.ArrayList;
      import java.util.List;
      import java.util.Queue;
      </pre>

      These are classes and interfaces from the Java library.

      • هنگامه

        Thank you 🙂

  • List<Integer> adjListForPoll = graph.get(poll – 1);

    This line seems to be a little hackish…. we can just go through the graph elements one by one… think of a scenario when the values of the graph nodes are string or some decimal values or any object…

    • You are absolutely correct Varun, this liberty wast taken because we know that these values were integers.. A more generic piece of code would really have to find all the connected vertices to the current vertex under consideration by a different mean.

      Would really appreciate if can add your code here. Thanks for pointing that out 🙂

      • we can try something like this ::

        package com.varun.datastructure.graphs;

        import java.util.ArrayList;

        import java.util.LinkedList;

        import java.util.Queue;

        public class BFS {

        public static void main(String[] args) {

        ArrayList graph = new ArrayList<>();

        vertexOfGraph v1 = new vertexOfGraph(1);

        vertexOfGraph v2 = new vertexOfGraph(2);

        vertexOfGraph v3 = new vertexOfGraph(3);

        vertexOfGraph v4 = new vertexOfGraph(4);

        vertexOfGraph v5 = new vertexOfGraph(5);

        vertexOfGraph v6 = new vertexOfGraph(6);

        ArrayList v1N = new ArrayList<>();

        v1N.add(v2);v1N.add(v3);

        v1.neighbour = v1N;

        ArrayList v2N = new ArrayList<>();

        v2N.add(v4);v2N.add(v3);v2N.add(v1);

        v2.neighbour=v2N;

        ArrayList v3N = new ArrayList<>();

        v3N.add(v2);v3N.add(v1);

        v3.neighbour=v3N;

        ArrayList v4N = new ArrayList<>();

        v4N.add(v2);v4N.add(v5);v4N.add(v6);

        v4.neighbour = v4N;

        ArrayList v5N = new ArrayList<>();

        v5N.add(v4); v5N.add(v6);

        v5.neighbour = v5N;

        ArrayList v6N = new ArrayList<>();

        v6N.add(v4);v6N.add(v5);

        v6.neighbour=v6N;

        graph.add(v1);

        graph.add(v2);

        graph.add(v3);

        graph.add(v4);

        graph.add(v5);

        graph.add(v6);

        bfs(graph,v1); // expected result ==> 1,2,3,4,5,6

        }

        private static void bfs(ArrayList graph, vertexOfGraph v1) {

        //graph is list of all the vertices

        ArrayList<vertexOfGraph> visited = new ArrayList<vertexOfGraph>();

        Queue<vertexOfGraph> temp = new LinkedList();

        temp.add(v1);

        visited.add(v1);

        while(!temp.isEmpty()){

        vertexOfGraph queueVal = temp.poll();

        for(int i = 0;i<queueVal.neighbour.size();i++){

        if(!visited.contains(queueVal.neighbour.get(i))){

        visited.add(queueVal.neighbour.get(i));

        temp.add(queueVal.neighbour.get(i));

        }

        }

        }

        for(vertexOfGraph v : visited){

        System.out.print(v.val +", ");

        }

        }

        }

        class vertexOfGraph {

        Object val;

        ArrayList<vertexOfGraph> neighbour;

        public vertexOfGraph(int val, ArrayList<vertexOfGraph> neighbour ){

        this.val=val;

        this.neighbour = neighbour;

        }

        public vertexOfGraph(int val){

        this.val=val;

        }

        }