RouteInGraph.java

// Problem: Route Between Nodes
// Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

class Graph {

	int size;
	boolean[] adjacencyMatrix[];

	public Graph(boolean adjacencyMatrix[][], int size) {
		this.adjacencyMatrix = adjacencyMatrix;
		this.size = size;
	}

	public boolean doesPathExist(int start, int end) {
		// perform Breadth First Search from both sides: start and end node
    
		LinkedList<Integer> startQueue = new LinkedList<Integer>();
		startQueue.addLast(start);

		LinkedList<Integer> endQueue = new LinkedList<Integer>();
		endQueue.addLast(end);

		// mark with 1 for visited from start
		// mark with 2 for visited from end
    		// default value is 0
		int visited[] = new int[this.size];
		Integer startNode = new Integer(0), endNode = new Integer(0);

		while (startQueue.size() > 0 || endQueue.size() > 0) {

			if (startQueue.size() > 0) {
				startNode = startQueue.removeFirst();
			}

			if (endQueue.size() > 0) {
				endNode = endQueue.removeFirst();
			}

			for (int i=0; i<this.size; ++i) {
				if (startNode != null && this.adjacencyMatrix[startNode.intValue()][i]) {
					//there is a vertex from node to i
					if (visited[i] == 0) {
						// need to mark it as visited
						visited[i] = 1;
					} else if (visited[i] == 2) {
						// it has been visited from the other side
						return true;
					}
					startQueue.addLast(new Integer(i));
				}

				if (endNode != null && this.adjacencyMatrix[i][endNode.intValue()]) {
					//there is a vertex from i to node
					if (visited[i] == 0) {
						// need to mark it as visited
						visited[i] = 2;
					} else if (visited[i] == 1) {
						// it has been visited from the other side
						return true;
					}
					endQueue.addLast(new Integer(i));
				}
			}
		}

		return false;
	}

}