Pages

Sunday, December 17, 2017

Breadth First Search(BFS) In Java

BFS or Breadth First Search is a very well-known graph traversal algorithm. The following java program performs this algorithm using adjacency list representation of graphs. Graphs may contain a cycle. To avoid processing a node twice, we used a Boolean array, name visited.



As an example, lets we have the following graph and we will start traversal from the node 1.



1.    Pick the starting node 1, push this node into the queue, mark Boolean array visited[1] = true. As we just visit node 1.
2.    Pop a node from the queue. We will get 1 as only one node in the queue.
3.    Find all adjacent nodes of 1.
4.    Node 1 has 4 adjacent (Neighbors) nodes: 2, 3, 4, 7. Push these nodes into the queue. And also mark visited array true for 2, 3, 4, 7.
5.     Pop a node from the queue, this time node 2 is available.
6.    Find all adjacent nodes of 2.
7.    Node 2 has only one adjacent node 5. Push this node into the queue again and mark as visited.
8.    Repeat this process until the queue is empty.

Let’s understand with the help of the following images:

Step 1:


Step 2:



Step 3:




Source code:

package com.monirthought.graph.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Breadth First Traversal or BFS implementation
 * 
 * @author Moniruzzaman Md
 *
 */
public class BFS {

 /* Boolean array to avoid duplicate process of each node */
 private boolean visited[];

 /* We use adjacency list representation for the graph */
 private LinkedList link[];

 public BFS(int totalNode) {

  /* Node number start with 1, so for 20 node, our array size must be 21 */
  /* Mark all the vertices as not visited, by default all are false */
  visited = new boolean[totalNode + 1];

  link = new LinkedList[totalNode + 1];

  /* Initialize each linkedList */
  for (int i = 1; i <= totalNode; i++) {
   link[i] = new LinkedList();
  }
 }

 public void doBFS(int start) {

  /* Queue for our BFS algorithm */
  Queue queue = new LinkedList();

  /* Push the starting node */
  queue.add(start);

  /* Marked the current node as visited */
  visited[start] = true;

  System.out.print(start);

  while (!queue.isEmpty()) {

   /* Dequeue a vertex from queue and print it */
   int current = queue.poll();

   /* Get all adjacent node of the dequeued node current */
   /* If a adjacent has not been visited yet, then mark it visited and enqueue it */
   for (int i = 0; i < link[current].size(); i++) {
    int adjacent = link[current].get(i);
    if (!this.visited[adjacent]) {
     this.visited[adjacent] = true;
     queue.add(adjacent);
     System.out.print(" " + adjacent);
    }
   }

  }
 }

 /**
  * Add each edge
  * 
  * @param start
  *            - starting node
  * @param end
  *            - ending node
  */
 public void addEdage(int start, int end) {
  link[start].add(end);
 }

 /**
  * Main method
  * 
  * @param args
  */
 public static void main(String[] args) {
  BFS bfs = new BFS(7);
  bfs.addEdage(1, 2);
  bfs.addEdage(1, 7);
  bfs.addEdage(1, 3);
  bfs.addEdage(2, 5);
  bfs.addEdage(3, 7);
  bfs.addEdage(5, 4);
  bfs.addEdage(1, 4);
  bfs.addEdage(4, 3);
  bfs.addEdage(4, 6);
  bfs.addEdage(4, 7);
  bfs.addEdage(6, 7);
  bfs.addEdage(5, 7);
  bfs.addEdage(7, 2);
  bfs.doBFS(1);
 }

}

Output:

If you run this program, it yields the following output
1 2 3 4 7 5 6

No comments:

Post a Comment