Graph Breadth First Search and Finding path between two vertices.

Breadth first search : Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a `search key'[1]) and explores the neighbor nodes first, before moving to the next level neighbors. Compare BFS with the equivalent, but more memory-efficient iterative deepening depth-first search and contrast with depth-first search.

The time complexity can be expressed as O(|V|+|E|),[5] since every vertex and every edge will be explored in the worst case.

Breadth-first search can be used to solve many problems in graph theory, for example:
Copying garbage collection, Cheney’s algorithm
Finding the shortest path between two nodes u and v (with path length measured by number of edges)
Testing a graph for bipartiteness
(Reverse) Cuthill–McKee mesh numbering
Ford–Fulkerson method for computing the maximum flow in a flow network
Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
Construction of the failure function of the Aho-Corasick pattern matcher.

package com.test.graph.algo;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;


public class BFS {
	
	private Graph.Vertex edgeTo[];
	
	public BFS(int size) {
		edgeTo = new Graph.Vertex[size];
	}
	
	public void bfs(Graph g, Graph.Vertex q){
		
		Queue<Graph.Vertex> queue = new ArrayBlockingQueue<Graph.Vertex>(g.getVertices().size());
		q.visited = true;
		System.out.println("Vertex : "+q);
		queue.add(q);
		Graph.Vertex w,v;
		while (!queue.isEmpty()) {
			v = queue.remove();
			while ( (w = getAdjUnvisitedVertex(v)) != null) {
				w.visited = true;
				queue.add(w);
				edgeTo[g.getIndexOf(w)] = v; // creating paths from v
				System.out.println("Vertex : "+w);
			}
		}
	}
	
	
	
	public void printPath(Graph g, Graph.Vertex source, Graph.Vertex target){
		
		Stack<Graph.Vertex> path = new Stack<Graph.Vertex>();
		for (Graph.Vertex v = target; v != source ; v = edgeTo[g.getIndexOf(v)]){
			path.add(v);
		}
		path.add(source);
		System.out.print("Path");
		while (!path.isEmpty()) {
			System.out.print("--"+path.pop());
		}
	}
	
		
	public static void main(String[] args) {
		
		List<Graph.Vertex> vertices = new ArrayList<Graph.Vertex>(); 
		Graph.Vertex A = new Graph.Vertex('A');
		Graph.Vertex B = new Graph.Vertex('B');
		Graph.Vertex C = new Graph.Vertex('C');
		Graph.Vertex D = new Graph.Vertex('D');
		Graph.Vertex E = new Graph.Vertex('E');
		Graph.Vertex F = new Graph.Vertex('F');
		Graph.Vertex G = new Graph.Vertex('G');
		Graph.Vertex H = new Graph.Vertex('H');
		vertices.add(A);
		vertices.add(B);
		vertices.add(C);
		vertices.add(D);
		vertices.add(E);
		vertices.add(F);
		vertices.add(G);
		vertices.add(H);
		
		List<Graph.Edge> edges = new ArrayList<Graph.Edge>();
		edges.add(new Graph.Edge(0,A,B));
		edges.add(new Graph.Edge(0,B,C));
		edges.add(new Graph.Edge(0,B,H));
		edges.add(new Graph.Edge(0,C,D));
		edges.add(new Graph.Edge(0,C,E));
		edges.add(new Graph.Edge(0,E,H));
		edges.add(new Graph.Edge(0,E,F));
		edges.add(new Graph.Edge(0,E,G));
		
		Graph g = new Graph(vertices, edges);
		
		BFS bfsObj = new BFS(g.getVertices().size());
		bfsObj.bfs(g, A);
		bfsObj.printPath(g, B, G);
	}
	
}