How to implement breadth first search algorithm (BFS) in java.

BFS (Breadth first search) Traversal algorithm can be applied to either Tree or Graph.

fig.1

Consider above bi-directional graph, where in there are 10 nodes. If one wants to traverse from node-0 to node-9 Using BFS then in below sequence, nodes will be discovered.

Start from node-0:
In, Hop-I, Nodes 1 & 7 will be discovered.
In, Hop-II, Nodes 2, 8 & 6 will be discovered.
In, Hop-III, Nodes 3 & 5 will be discovered.
In, Hop-IV, Node 4 will be discovered.
In, Hop-V, Node 9 will be discovered.

Solution:
Below is the implementation of BFS in java using Queue as a data structure,

package com.mayank4java.algorithms;

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

public class BFSTraversalAlgorithm {
private int[][] graph;
private boolean[] isVisited;

public BFSTraversalAlgorithm(int noOfNodes) {
graph = new int[noOfNodes][noOfNodes];
isVisited = new boolean[noOfNodes];
}

public void addLink(int srcNode, int destNode) {
graph[srcNode][destNode] = 1;
graph[destNode][srcNode] = 1;
}

public void doBFS(int startNode) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(startNode);
isVisited[startNode] = true;
while (!queue.isEmpty()) {
int a = (int) queue.remove();

System.out.println("@Node : " + a);
int[] row = graph[a];

for (int i = 0; i < row.length; i++) {

if (row[i] != 0 && !(isVisited[i])) {
queue.add(i);
isVisited[i] = true; /*
* Imp to mark node as visited here
* just after adding to the queue
* instead of removing from queue
*/
}
}
}
}

public static void main(String[] args) {
BFSTraversalAlgorithm graph = new BFSTraversalAlgorithm(10);

graph.addLink(0, 1);

graph.addLink(0, 7);

graph.addLink(7, 1);

graph.addLink(1, 2);

graph.addLink(7, 8);

graph.addLink(7, 6);

graph.addLink(2, 8);

graph.addLink(8, 6);

graph.addLink(6, 5);

graph.addLink(2, 5);

graph.addLink(2, 3);

graph.addLink(3, 5);

graph.addLink(3, 4);

graph.addLink(5, 4);

graph.addLink(4, 9);

graph.doBFS(0);
}

}

That is it!😃

Hope this post helped you.Also don't forget to share and leave your comments below.