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

Have you met this question in a real interview?

Yes

Example

Given graph:

A-----
>
B-----
>
C
 \     |
  \    |
   \   |
    \  v
     -
>
D-----
>
E

fors = Bandt = E, returntrue

fors = Dandt = C, returnfalse

1. dfs

if go dfs directly will exceed time limit on the final large test case, we need to cut the operation to remove the doubly directed nodes to go backwards, like A -> B and B -> A, so we don't need the path of B -> A because A and its path is already being weighted. we can do this in place to save the space complexity by changing the points that we had walked to -1

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) {
 *         label = x;
 *         neighbors = new ArrayList<DirectedGraphNode>();
 *     }
 * };
 */


public class Solution {
    /*
     * @param graph: A list of Directed graph node
     * @param s: the starting Directed graph node
     * @param t: the terminal Directed graph node
     * @return: a boolean value
     */
    //recursion

    public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
        // write your code here


        if (!graph.contains(s) || !graph.contains(t)) {
            return false;
        }

        if (s.label != t.label && s.neighbors == null) {
            return false;
        }

        if (s.label == t.label) {
            return true;
        }

        for (int i = 0; i < s.neighbors.size(); i++) {
            if (s.neighbors.get(i).label == t.label) {
                return true;
            }

            if (s.neighbors.get(i).label == -1) {
                continue;
            }

            if(hasRoute(graph, s.neighbors.get(i), t)) {
                return true;   
            }
            s.neighbors.get(i).label = -1;
        }

        return false;


    }
}

1. bfs

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) {
 *         label = x;
 *         neighbors = new ArrayList<DirectedGraphNode>();
 *     }
 * };
 */


public class Solution {
    /*
     * @param graph: A list of Directed graph node
     * @param s: the starting Directed graph node
     * @param t: the terminal Directed graph node
     * @return: a boolean value
     */
    //non-recursion bfs
    public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
        // write your code here
        if (!graph.contains(s) || !graph.contains(t)) {
            return false;
        }

        //see if they are the same point
        if (s.label == t.label) {
            return true;
        }

        boolean ans = false;
        Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
        queue.add(s);

        while (!queue.isEmpty()) {
            //seperate level
            int size = queue.size();
            DirectedGraphNode cur = queue.poll();

            for (int i = 0; i < size; i++) {
                if (cur.label == -1) {
                    continue;
                }

                if (cur.label == t.label) {
                    return true;
                }

                cur.label = -1;

                for (int j = 0; j < cur.neighbors.size(); j++) {

                    queue.offer(cur.neighbors.get(j));
                }


            }
        }

        return false;
    }
}