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

DGraph.java

/* Depth First Search	*/

import java.util.ArrayList;

public class DGraph {
	private int V;
	private ArrayList<Integer>[] adj;
	private boolean[] marked;
	
	@SuppressWarnings("unchecked")
	public DGraph(int V) {
		this.V = V;
		adj = (ArrayList<Integer>[]) new ArrayList[V];
		for (int v = 0; v < V; v++)
			this.adj[v] = new ArrayList<Integer>();
	}
	
	public void addEdge(int v, int w) {
		adj[v].add(w);
	}
	
	public Iterable<Integer> adj(int v) {
		return this.adj[v];
	}
	
	public int V() {
		return V;
	}
	
	public boolean hasPath(int v, int w) {
		marked = new boolean[V];
		dfs(v);
		if (marked[w]) return true;
		else return false;
	}
	
	private void dfs(int v) {
		marked[v] = true;
		for (int w : adj[v]) {
			if (!marked[w]) dfs(w);
		}
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(this.V + " vertices\n");
		for (int v = 0; v < V; v++) {
			sb.append(v + ": ");
			for (int w: adj[v]) 
				sb.append(w + " ");
			sb.append("\n");
		}
		return sb.toString();
	}
	
	public static void main(String[] args) {
		DGraph G = new DGraph(6);
		/*		0: 3 5
		 * 		1: 4
		 *		2: 3 4
		 *		3: 1 4
		 *		4: 3 5
		 *		5: 4
		 */
		G.addEdge(0, 3);G.addEdge(0, 5);
		G.addEdge(1, 4);
		G.addEdge(2, 3);G.addEdge(2, 4);
		G.addEdge(3, 1);G.addEdge(3, 4);
		G.addEdge(4, 3);G.addEdge(4, 5);
		G.addEdge(5, 4);
		
		if (G.hasPath(0, 4))
			System.out.println("Yes");
		else System.out.println("No");
		
		if (G.hasPath(2, 0))
			System.out.println("Yes");
		else System.out.println("No");

	}
	
}