Created
July 10, 2014 01:14
-
-
Save nealhu/ff50192e189ae3f01e4f to your computer and use it in GitHub Desktop.
CC_4_2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Cracking the Coding Interview | |
// 4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes. | |
import java.util.Set; | |
import java.util.HashSet; | |
import java.util.Queue; | |
import java.util.LinkedList; | |
class Node { | |
public int val; | |
public Set<Node> neighbors; | |
Node(int v) { | |
val = v; | |
neighbors = new HashSet<Node>(); | |
} | |
} | |
class RouteInGraph { | |
public static boolean areConnected(Node src, Node dest) { | |
HashSet<Node> visited = new HashSet<Node>(); | |
Queue<Node> q = new LinkedList<Node>(); | |
q.add(src); | |
while(!q.isEmpty()) { | |
Node tmp = q.poll(); | |
if (tmp == dest) { | |
return true; | |
} | |
visited.add(tmp); | |
for(Node n: tmp.neighbors) { | |
if (!visited.contains(n)) { | |
// hasn't visited | |
q.add(n); | |
} | |
} | |
} | |
return false; | |
} | |
public static void main(String[] args) { | |
Node n1 = new Node(0); | |
Node n2 = new Node(1); | |
Node n3 = new Node(2); | |
Node n4 = new Node(3); | |
Node n5 = new Node(5); | |
Node n6 = new Node(6); | |
n1.neighbors.add(n2); | |
n1.neighbors.add(n3); | |
n2.neighbors.add(n4); | |
n4.neighbors.add(n5); | |
n4.neighbors.add(n1); | |
n3.neighbors.add(n5); | |
n3.neighbors.add(n3); | |
assert !areConnected(n1, n6); | |
assert !areConnected(n6, n1); | |
assert areConnected(n1, n5); | |
assert !areConnected(n5, n1); | |
assert areConnected(n1, n2); | |
assert areConnected(n1, n3); | |
assert areConnected(n1, n4); | |
assert areConnected(n4, n1); | |
assert areConnected(n3, n1); | |
assert !areConnected(n5, n6); | |
assert areConnected(n3, n3); | |
System.out.println("Tests Passed"); | |
} | |
} |
jason51122
commented
Jul 10, 2014
- Good job.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment