Graph Breadth-First traversal

For doing anything meaningful with graphs; we should be able to traverse it in a certain order. Traversal helps in solving problems like searching for a vertex/edge, check if a path exists between two vertices, check if the graph is connected, check if the graph contains loop etc. 

There are two approaches for traversing a graph, BFS, and DFS. This post, I will be focusing on Breadth First Search (or traversal). It begins at a given root or origin node/vertex and visits all neighboring vertices. Then it starts visiting neighbors of its neighbors. This process is continued until all nodes are visited. It uses a queue to keep track of yet to be visited nodes. It also uses a separate data structure to mark all the visited nodes, this is required to make sure that the algorithm doesn't traverse the same node repetitively (if a loop exists).

In the above diagram, traversal starts at node 1. Afterwards, it visits its neighbors 2,5 and 6.

Breadth-First Search

Below diagram shows the order in which the nodes/vertices gets traversed in each step. It starts with vertex 1 and then finally ends at node 4. Below Java implementation use

BFS Traversal

Implementation

Below Java implementation uses Graph implementation from this Graph.java. 

package graph.algo;

import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;

/**
 * Depth-First Traversal of a graph represented as adjacency list
 * 
 * @author Siddheshwar
 * 
 */
public class BFS<V> {
 private Graph<V> graph; // graph on which dfs will be performed
 private Queue<V> queue;
 private Set<V> visited;

 public BFS(Graph<V> graph) {
  this.graph = graph;
  queue = new LinkedList<>();
  visited = new LinkedHashSet<>();  // to maintain the insertion order
 }

 /**
  * Return true if vertex is already visited
  * @param i
  * @return
  */
 private boolean isVertexVisited(V i) {
  return this.visited.contains(i);
 }

 /**
  * Add vertex to visited
  * @param i
  */
 private void markAsVisited(V i) {
  this.visited.add(i);
 }

 /**
  * Breadth-first traversal of the graph
  * 
  * @param source
  */
 public void traverse(V source) {
  Objects.requireNonNull(source, "source is manadatory!");
  if (this.graph == null || this.graph.isEmpty()) {
   throw new IllegalStateException(
     "Valid graph object is required !!!");
  }

  queue.add(source);
  System.out.print(" " + source);
  this.markAsVisited(source);

  while (!queue.isEmpty()) {
   V v = queue.remove();

   List<V> neighbors = graph.getAdjacentVertices(v);
   if (!neighbors.isEmpty()) {
    for (V n : neighbors) {
     if (!this.isVertexVisited(n)) {
      visited.add(n);
      System.out.print(" " + n);
      queue.add(n);
     }
    }
   }
  }
 }

 // test method
 public static void main(String[] args) {
  Graph<Integer> graph = new Graph<>();
  
  graph.addEdge(1, 2);
  graph.addEdge(1, 5);
  graph.addEdge(1, 6);
  graph.addEdge(2, 3);
  graph.addEdge(2, 5);
  graph.addEdge(3, 4);
  graph.addEdge(5, 4);

  graph.addEdge(2, 1);
  graph.addEdge(5, 1);
  graph.addEdge(6, 1);
  graph.addEdge(3, 2);
  graph.addEdge(5, 2);
  graph.addEdge(4, 3);
  graph.addEdge(4, 5);

  BFS<Integer> bfs = new BFS<>(graph);
  
  System.out.print("BFS -->");
  bfs.traverse(1);
  
  //validation
  /**
   * after traversal; queue should be empty. And visited should have
   * vertices in BFS order
   */
  System.out.println("\nIs Queue empty :"+ 
   (bfs.queue.isEmpty() ? " yes " : "no"));
  System.out.println("visited :" + bfs.visited);
 }

}

Output:
BFS --> 1 2 5 6 3 4
Is Queue empty : yes 

visited :[1, 2, 5, 6, 3, 4]

Time Complexity

Assuming above implementation of Graph i.e. Adjacency List, |V| is the number of vertices and |E| is number of edges. Each vertex is enqueued and dequeued at most once. Scanning for neighbors takes O(|E|) time. 

So complexity is O(|V|+|E|)

References:
http://en.algoritmy.net/article/45430/Depth-first-search

--

happy learning !!!