Breadth First Traversal of a Graph

Traversal of the graph is used to perform task such as searching for certain node. The graph may contain cycles, so we may come to same node again while traversing. To avoid it, we need to keep track of visited node, so we can not come again to the same node, we use a boolean visited array.

Lets understand it with example. In the following graph, we start traversing from vertex 0 when we come to vertex 1, we look for all adjacent vertices of it. 0 is also adjacent of vertex 1. if we don't mark visited vertex, we again process the vertex 0 and it will go into non-terminating loop. A breadth first search of following graph is 0, 1, 2,3.

Following is the java implementation of breadth first traversal of a graph.

import java.util.Iterator;
import java.util.LinkedList;

//This program will print the breadth first traversal of a graph from a given source vertex
public class BreadthFirstTraversal {
 private int v; // no of vertices in a graph
 private LinkedList<Integer> adj[]; // array of linked list for adjacency
        // list representation

 public BreadthFirstTraversal(int v) {
  this.v = v;
  adj = new LinkedList[v];
  for (int i = 0; i < v; i++) {
   adj[i] = new LinkedList<Integer>();
  }
 }

 // method to add an edge into a graph
 public void add(int i, int j) {
  adj[i].add(j);
 }

 // print BFS traversal from a given source vertex s
 public void BFS(int s) {
  // mark all the vertices as not visited
  boolean visited[] = new boolean[this.v];
  // create a queue for BFS
  LinkedList<Integer> queue = new LinkedList<Integer>();
  // mark the current vertex as visited and enqueue it
  queue.add(s);
  visited[s] = true;
  while (queue.size() != 0) {
   // dequeue a vertex from queue and print it
   s = queue.pop();
   System.out.print(s + " ");

   // create an iterator, to get all the adjacent vertices of dequeued
   // vertex s
   // if the adjacent vertex is not visited then mark it visited and
   // enqueue it
   Iterator<Integer> i = adj[s].iterator();
   while (i.hasNext()) {
    int n = i.next();
    if (!visited[n]) {
     visited[n] = true;
     queue.add(n);
    }
   } // end of inner while loop

  } // end of outer while loop
 }

 public static void main(String[] args) {
  BreadthFirstTraversal g = new BreadthFirstTraversal(4);
  g.add(0, 1);
  g.add(0, 2);
  g.add(1, 0);
  g.add(1, 2);
  g.add(1, 3);
  g.add(3, 3);

  System.out.println("Following is Breadth First Traversal "
                 + "(starting from vertex 0)");

  g.BFS(0);
 }
}

Output of above program is shown below:

Following is Breadth First Traversal (starting from vertex 0)
0 1 2 3

In the above code, it traverse to the vertices that are reachable from the source node. All the vertices may not be reachable from the source vertex(in case of disconnected graph).

Below code is the java implementation of breadth first search that will cover disconnected graph or vertices are not reachable from given source vertex.

We can modify the above BFS method to do traversal starting from all nodes one by one.

You can consider the below disconnected directed graph.

import java.util.LinkedList;

//This program will print the breadth first traversal of a disconnected graph
//from a given source vertex
public class BreadthFirstTraversal {
 private int v; // no of vertices in a graph
 private LinkedList<Integer> adj[]; // array of linked list for adjacency
              // list representation

 public BreadthFirstTraversal(int v) {
  this.v = v;
  adj = new LinkedList[v];
  for (int i = 0; i < v; i++) {
   adj[i] = new LinkedList<Integer>();
  }
 }

 // method to add an edge into a graph
 public void add(int i, int j) {
  adj[i].add(j);
 }

 // print BFS traversal from a given source vertex s
 public void BFSUtil(int s, boolean visited[]) {
  // create a queue for BFS
  LinkedList<Integer> queue = new LinkedList<Integer>();
  // mark the current vertex as visited and enqueue it
  queue.add(s);
  visited[s] = true;
  while (queue.size() != 0) {
   // dequeue a vertex from queue and print it
   s = queue.pop();
   System.out.print(s + " ");

   // create an iterator, to get all the adjacent vertices of dequeued
   // vertex s
   // if the adjacent vertex is not visited then mark it visited and
   // enqueue it
   Iterator<Integer> i = adj[s].iterator();
   while (i.hasNext()) {
    int n = i.next();
    if (!visited[n]) {
     visited[n] = true;
     queue.add(n);
    }
   } // end of inner while loop

  } // end of outer while loop
 }

 public void BFS(int s) {
  // mark all the vertices as not visited
  boolean visited[] = new boolean[this.v];

  for (int i = 0; i < this.v; i++) {
   if (visited[i] == false)
    BFSUtil(i, visited);
  }

 }

 public static void main(String[] args) {
  BreadthFirstTraversal g = new BreadthFirstTraversal(5);
  g.add(0, 1);
  g.add(0, 2);
  g.add(1, 0);
  g.add(1, 2);
  g.add(3, 3);
  g.add(2, 4);

  System.out.println("Following is Breadth First Traversal "
                            + "(starting from vertex 0)");

  g.BFS(0);
 }
}

Output of above program is shown below:

Following is Breadth First Traversal (starting from vertex 0)
0 1 2 4 3

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.