Graph Traversal: Breadth First Search

Breadth First Search (BFS) is a fundamental graph-traversal technique and you could use it of find it being used in a wide range of applications. For a full explanation of the technique check this link, or this link.

The parent array in BFS is very useful for finding interesting paths through a graph; the parent relation defines a TREE OF DISCOVERY with the starting node as the root of the tree.

Because vertices are discovered in order of increasing distance from the root, the tree of discovery contains minimum-length paths from the root to each node.

The time complexity of a BFS implementation is: O(M + N) , that is, it runs in linear time as a function of the sum of the cardinalities of the vertex and edge sets.
Two example application problems where BFS plays a role are:

• Connected Components
• Two-Coloring (Bipartite checking)

The following is a generic implementation of BFS:

 
package com.medina.toolbox.graphs.bfs;

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;

import com.medina.toolbox.graphs.EdgeNode;
import com.medina.toolbox.graphs.Graph;
import com.medina.toolbox.graphs.GraphTraversal;
import com.medina.toolbox.graphs.TraversalProcedures;
import com.medina.toolbox.graphs.TraversalProceduresGeneric;

public class BreadthFirstSearch extends GraphTraversal  {

 public BreadthFirstSearch(Graph g, TraversalProcedures proc) {
  super(g, proc);
 }
 
 public void traverse(int start) { 

  /* Queue to keep track of work to be done */
  Queue q = new LinkedList();
  
  q.add(start);
  discovered[start] = Boolean.TRUE;
  
  while (!q.isEmpty()) {
   
   int v = q.remove();
   
   /* Invoke PROCESS VERTEX EARLY functionality */
   proc.processVertexEarly(v);
   
   /* Mark vertex v as processed */
   processed[v] = Boolean.TRUE;
   
   /* Grab adjacency list for node v */
   EdgeNode p = g.getEdges().get(v);
   
   /* Explore all adjacencies of vertex v */
   while (p != null) {
    
    int y = p.y;
    
    if (!processed[y] || g.isDirected()) {
     proc.processEdge(v, y);
    }
    
    if (!discovered[y]) {
     q.add(y);
     discovered[y] = Boolean.TRUE;
     parent[y] = v;
    }
    
    p = p.next;
    
   }
   
   proc.processVertexLate(v);
  }
  
 }
 

And we can add the following Main function to the class definition in order to try it:

 public static void main(String[] args) {

  Graph g = null;
  try {
   
   g = Graph.readFromFile("data/graph01.txt");
   g.printGraph();
   
   TraversalProceduresGeneric proc = new TraversalProceduresGeneric();
   BreadthFirstSearch bfs = new BreadthFirstSearch(g, proc);
   bfs.traverse(0);
   proc.finalize();
   
  } catch (IOException e) {   
   e.printStackTrace();
  }
 }

}

There are several important elements to note in this BFS implementation:

• There is a class we did not post, EdgeNode, which is simply represents the notion of an edge (source, destination, weight, and so on); what we said we were using an adjacency list for the graph implementation, we meant a list of EdgeNodes for each vertex in the graph.
• The constructor receives an instance of an implementation of the functionality API we described before (TraversalProcdures). We passed the appropriate implementation depending on what we want to use BFS for. You will see how soon.
• The BFS traversal is invoked through the traverse method, which receives the starting node of the search as a parameter.
• An implementation of the Queue interface is used; in this case we chose to use a LinkedList. This structure is used by BFS to keep track of the work that needs to be done.
• Three calls to the functionality API are used: processVertexEarly(), which is invoked the first time is popped out of the queue to be processed; processEdge(), which is called when processing the adjacency list of a given vertex; and processVertexLate(), which is invoked once BFS is done with a vertex.
• Finally, notice how the state (i.e. discovered, processed, parent arrays) is updated as the BFS proceeds with the traversal.