Skip to content

Instantly share code, notes, and snippets.

@chouclee
Created July 3, 2014 05:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chouclee/60c5d74e6fa206e656c7 to your computer and use it in GitHub Desktop.
Save chouclee/60c5d74e6fa206e656c7 to your computer and use it in GitHub Desktop.
[CC150][4.2] Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
/* 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");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment