Question4_2.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
 * 
 * Time  Complexity: O(v+e)
 * Space Complexity: O(v)
 */

public class Question4_2 {
    public boolean existRoute(Node src, Node dst) {
        if (src == null || dst == null) {
            return false;
        }
        
        HashSet<Node> hash = new HashSet<Node>();
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.addFirst(src);
        while (!queue.isEmpty()) {
            Node node = queue.removeLast();
            hash.add(node);
            if (node == dst) {
                return true;
            }
            for (Node neighbor : node.neighbors) {
                if (!hash.contains(neighbor)) {
                    queue.addFirst(neighbor);
                }
            }
        }
        
        return false;
    }
    
    
    public static void main(String[] args) {
        Question4_2 question4_2 = new Question4_2();
        System.out.println(question4_2.existRoute(null, null));
        Node src = new Node(0);
        src.neighbors.add(new Node(1));
        src.neighbors.add(new Node(2));
        src.neighbors.get(0).neighbors.add(new Node(3));
        src.neighbors.get(0).neighbors.get(0).neighbors.add(new Node(4));
        Node dst = new Node(5);
        src.neighbors.get(0).neighbors.get(0).neighbors.add(dst);
        System.out.println(question4_2.existRoute(src, dst));
    }
}


class Node {
    int value;
    ArrayList<Node> neighbors;
    
    public Node(int value) {
        this.value = value;
        neighbors = new ArrayList<Node>();
    }
}