# 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)

```java
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:**

![](https://2628390332-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M0RnkuvOeqe0clAIN1b%2F-M95oE7fMN6JVNkEesob%2F-M95oh2MetlrsrIGDshA%2Fimage.png?alt=media\&token=8627186f-71d8-4d2a-8205-00c27ccf39f6)

```java
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;
}
```

####
