## Tuesday, 24 May 2016

### Breadth-first search (BFS) Implemetation in Java

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

public class GraphBFS {

// No. of vertices
private int vertives;

//Adjacency Lists - Edges
private LinkedList<Integer> adj[];

GraphBFS(int vertices) {
vertives = vertices;
adj = new LinkedList[vertices];
for (int i=0; i<vertices; ++i) {
adj[i] = new LinkedList<Integer>();
}
}

void addEdge(int v,int w) {
adj[v].add(w);
}

private void traverseBFS(int node) {
/** Mark true if vertices are visited. */
boolean visited[] = new boolean[vertives];

/** Create a queue for BFS */
LinkedList<Integer> queue = new LinkedList<Integer>();

/** mark start node as visited by default. */
visited[node] = true;
queue.add(node);

while(!queue.isEmpty()) {

/** poll the first element of queue. */
node = queue.poll();

System.out.print(node+" ");

/** add all the nearest node of processing node. */
Iterator<Integer> iter = adj[node].listIterator();
while (iter.hasNext()) {
int next = iter.next();
if (!visited[next]) {
visited[next] = true;
queue.add(next);
}
}
}
}

public static void main(String args[]) {

/** Create a graph of size . */
GraphBFS graph = new GraphBFS(4);

/** Add edges in the graph.*/
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 2);
graph.addEdge(3, 1);

System.out.println("BFS Traversal : ");

/** start BS from any given node.*/
graph.traverseBFS(1);
}
}
Output
BFS Traversal:
1 2 0 3