Li Kou interview question 04.01 Path between nodes

subject ：

analysis ：

        This can be done in the form of establishing adjacency tables , Use one hashmap Store which nodes each node can point to , And then start Put in queue , Find out the correspondence key The node that can be reached and has not been visited in the value , Put it in the queue and set the value of the corresponding Boolean array to true, If the queue is empty, there is no path .

Code ：

class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        boolean[] b=new boolean[n];
        HashMap<Integer,List<Integer>> hhash=new HashMap<Integer,List<Integer>>();
        Queue<Integer> q=new LinkedList();
        for(int i=0;i<graph.length;i++){
            if(!hhash.containsKey(graph[i][0])){
                hhash.put(graph[i][0],new ArrayList());
            }
            List list=hhash.get(graph[i][0]);
            list.add(graph[i][1]);
        }
        q.offer(start);
        b[start]=true;
        while(!q.isEmpty()){
            int s=q.poll();
            if(!hhash.containsKey(s)){
                continue;
            }else{
                List list=hhash.get(s);
                for(int j=0;j<list.size();j++){
                    int i=(int)list.get(j);
                    if(!b[i]){
                        if(i==target){
                            return true;
                        }else{
                            b[i]=true;
                            q.offer(i);
                        }
                    }
                }
            }
        }
        return false;
    }
}