CC4.2.java

/*4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.*/
/* BFS or DFS */
Compare DFS & BFS:
 - DFS is more simple 'cause it can be implement by recursion
 - BFS may find the shortest way, well DFS one node very deep ever before visit the immediate node

public enum State {
    Visited, Unvisited, Visiting;
}
class Node {
    int label;
    State state;
    ArrayList<Node> adj = new ArrayList<Node>();
    public Node(int label) {
        this.label = label;
        this.state = State.Unvisited;
    }
}
class Graph {
    ArrayList<Node> nodes = new ArrayList<Node>();
    public ArrayList<Node> getNodes() {
        return this.nodes;
    }
    
}

// Solution 1 BFS
public class Solution {
    public static boolean search(Graph g, Node start, Node end) {
        LinkedList<Node> que = new LinkedList<Node>();
        for(Node n : g.getNodes()) {
            n.state = State.Unvisited;
        }
        start.state = Visiting;
        que.offer(start);
        while(!que.isEmpty()) {
            Node cur = que.poll();
            for(Node neighbor : cur.adj) {
                if(neighbor==end) return true;
                if(neighbor.state==State.Unvisited) {
                    neighbor.state = State.Visiting;
                    que.offer(neighbor);
                }
            }
            cur.state = State.Visited;
        }
        return false;
    }
}

// Solution 2 DFS
public class Solution  {
    public boolean Search (Graph g, Node start, Node end) {
        Stack<Node> st = new Stack<Node>();
        for(Node node : g.getNodes()) {
            node.state = State.Unvisited;
        }
        start.state = State.Visiting;
        st.push(start);
        while(!st.isEmpty()) {
            Node cur = st.pop();
            if(cur.state==State.Visited)
                continue;
                
            for(Node neighbor : cur.adj) {
                if(neighbor==end) return true;
                neighbor.state = State.Visiting;
                st.push(neighbor);
            }
            cur.state = State.Visited;
        }
        return false;
    }
}