Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

CC150-4.2-DirectedGraph.java

package POJ;

import java.lang.reflect.Array;
import java.util.ArrayList;

public class DirectedGraph {
	private ArrayList<Integer>[] graph;
	public DirectedGraph(int n){
		graph=(ArrayList<Integer>[])new ArrayList[n];
		for(int i=0;i<n;i++){
			graph[i]=new ArrayList<Integer>();
		}
	}
	public void addEdge(int from,int to){
		graph[from].add(to);
	}
	public ArrayList<Integer> endVertices(int v){
		return graph[v];
	}
	public int size(){
		return graph.length;
	}
}

CC150-4.2-Main.java

package POJ;

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

public class Main{

	/**
	 * 4.2 Given a directed graph, design an algorithm to find out whether
	 * there is a route between two nodes.
	 * 
	 * DFS is a bit simpler to implement since it can be done with simple recursio.
	 * BFS can also be useful to find the shortest path, whereas DFS may traverse one
	 * adjacent node very deeply before ever going onto the immediate neighbors.
	 * 
	 *  @Runtime & spaces
	 * 	runtime: O(n)
	 * 	space: O(n)
	 * 
	 */
	
	private DirectedGraph graph;

	public Main(DirectedGraph g) {
		// TODO Auto-generated constructor stub
		graph = g;
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		DirectedGraph g = new DirectedGraph(4);
		g.addEdge(0, 1);
		g.addEdge(0, 2);
		g.addEdge(2, 1);
		g.addEdge(2, 3);
		g.addEdge(3, 2);
		Main so = new Main(g);
		System.out.println(so.hasRoutesBFS(1, 3));
		System.out.println(so.hasRoutesBFS(3, 1));
		System.out.println(so.hasRoutesBFS(3, 0));
	}


	private boolean hasRoutesBFS(int start, int end) {
		// BFS
		if (start < 0 || start >= graph.size() || end < 0
				|| end >= graph.size())
			return false;
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] isVisited = new boolean[graph.size()];
		queue.add(start);
		while (!queue.isEmpty()) {
			int temp=queue.remove();
			if(temp==end)
				return true;
			if(isVisited[temp])
				continue;
			isVisited[temp]=true;
			for(int v:graph.endVertices(temp))
				queue.add(v);
		}
		return false;
	}
}