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

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-if-path-exists-in-directed-graph-problem/.

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.