BFS

The Time complexity of BFS is O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used, where V stands for vertices and E stands for edges.

It is to get the min length of the path to the destination of a graph.

Template (duplicate will not happen, ex Tree traversal)

void dfs(TreeNode root, TreeNode target){

    Queue<node> queue = new LinkedList<>();
    queue.add(root);
    int step = 0;
    while(!queue.isEmpty()){
        int size = queue.size();
        step++;
        for(int i = 0; i < size; i++){
            TreeNode curent = queue.poll();
            if(current == target) return step;
            for (Node next : curent.childs) {
                queue.add(next);
            }
        }
    }    
    return -1;
}

Template (Duplicate might happen during the iteration, connected Graph)

node要再加入queue時，同時加進去visited set中，否則可能會衍伸重複巡查。

ex:

void dfs(TreeNode root, TreeNode target){

    Queue<TreeNode> queue = new LinkedList<>();
    HashSet<TreeNode> visited = new HashSet<>();
    queue.add(root);
    visited.add(root);
    int step = 0;
    while(!queue.isEmpty()){
        int size = queue.size();
        step++;
        for(int i = 0; i < size; i++){
            TreeNode curent = queue.poll();
            if(current == target) return step;
            for (Node next : curent.childs) {
                if(!visited.contains(next)){ //add checking for visted or not
                    queue.add(next);
                    visited.add(next); //add to visited
                }
            }
        }
    }    
    return -1;
}