Skip to content

Instantly share code, notes, and snippets.

@KodeSeeker
Last active December 14, 2015 22:29
Show Gist options
  • Save KodeSeeker/5159084 to your computer and use it in GitHub Desktop.
Save KodeSeeker/5159084 to your computer and use it in GitHub Desktop.
Given a directed graph, design an algorithm to find out whether there is a route between two nodes
public enum State {
Unvisited, Visited, Visiting;
}
// let the start node and the end node be both the nodes.
// Implementation using DFS.
public static boolean search(Graph g, Node start, Node end) {
LinkedList<Node> stack = new LinkedList<Node>(); // operates as Stack
for (Node u : g.getNodes()) {
u.state = State.Unvisited;
}
start.state = State.Visiting;
stack.add(start);
Node u;
while(!stack.isEmpty())
{
u = stack.removeFirst(); // i.e., pop()
if (u != null) {
for (Node v : u.getAdjacent()) {
if (v.state == State.Unvisited) {
if (v == end) {
return true;
}
else {
v.state = State.Visiting;
stack.add(v);
}
}
}
u.state = State.Visited;
}
}
return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment