## Sunday, February 9, 2014

### Problem :

Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second.

### Solution

We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph.

BFS to check the connectivity
```public enum State {
Unvisited, Visited, Visiting;
}

public static boolean search(Graph g, Node start, Node end) {
for (Node u : g.getNodes()) {
u.state = State.Unvisited;
}
start.state = State.Visiting;
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;
}
}
}
u.state = State.Visited;
}
}
return false;
}
```

Like wise we can also apply DFS.
```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 {
stack.push(child);
}
}
}
}
return false;
}
```

Time complexity: O(|V|+|E|). Space complexity: O(|V|).

Use Stack for DFS. Use Queue for BFS.

1. 1. 