Sunday, February 9, 2014

Find if there is a path between two vertices in a directed graph

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) {
    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 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 {
                    visited.add(curr);
                    for (Integer child : g.adj(curr))
                        stack.push(child);
                }
            }
        }
    }
    return false;
}

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


Use Stack for DFS. Use Queue for BFS.

2 comments:

  1. Why do you need to have 3 states ("Visited, "Unvisited", and "Visiting")? It seems like we do the same thing - adding the node to the queue - if it's unvisited, but there is no functional distinction between visited and visiting (in either state we skip it - we won't enqueue it and we won't check against it). So, aside from debugging, I don't see any benefit of having it. Am I wrong?

    ReplyDelete
    Replies
    1. Hi..I agree that only visited and unvisited was enough.Thanks.

      Delete