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

**My initial thoughts:**

Starting from the source, using DFS to traverse the graph to check if we arrive at the target.

**My initial codes:**

public static boolean isRouteBetween(Digraph g, Integer start, Integer end) {
Stack<Integer> stack = new Stack<Integer>();
Set<Integer> visited = new HashSet<Integer>();
if (start != null) {
stack.push(start);
while (!stack.isEmpty()) {
Integer curr = stack.pop();
if (!visited.contains(curr)) {
if (curr.equals(end))
return true;
else {
visited.add(curr);
for (Integer child : g.adj(curr))
stack.push(child);
}
}
}
}
return false;
}

Comments:

- Time complexity: . Space complexity:
- Use Stack for DFS. Use Queue for BFS.

**Solution:**

public enum State {
Unvisited, Visited, Visiting;
}
public static boolean search(Graph g, Node start, Node end) {
LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack
for (Node u : g.getNodes()) {
u.state = State.Unvisited;
}
start.state = State.Visiting;
q.add(start);
Node u;
while (!q.isEmpty()) {
u = q.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;
q.add(v);
}
}
}
u.state = State.Visited;
}
}
return false;
}

### Like this:

Like Loading...

*Related*

## 1 Comment

(+add yours?)