> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/chapter1/breath-first-search.md).

# Breadth-First Search

## Breadth-First Search

## 1. BFS in Graph

### (1) Summary

* Create adjacent list or adjacent matrix (prefer adjacent list since it is more space efficient) to build the graph mode given the relations
* If each node can only be visited once, we should use an boolean array to check if the node has been visited
* Pop a node from queue, and iterate over the node's neighbors and put them to the queue

### (2) Template

```java
class UndirectedGraphNode {
      int label;
      List<UndirectedGraphNode> neighbors;
      UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
};

public void BFSInGraph (UndirectedGraphNode node) {
     if (node == null) {
          return;
     }  

     Queue<UndirectedGraphNode> queue = new LinkedList<>();
     queue.add(node);

     while (!queue.isEmpty()) {
        UndirectedGraphNode curNode = queue.remove();

        for (UndirectedGraphNode nextNode : curNode.neighbors) {
            queue.add(nextNode);
        }
     }
}
```

## 2. BFS in Matrix

### (1) Summary

* Every cell in the matrix will be visited only once using BFS
* Can calculate the distance to a given cell:  [Shortest Distance from All Buildings](https://leetcode.com/problems/shortest-distance-from-all-buildings/?tab=Description)
* If every cell can be visited only once, we can use either a boolean array to check if a cell has been visited or change the current value in the cell to avoid visiting it again: [Surrounded Regions](https://leetcode.com/problems/surrounded-regions/?tab=Description), (Here, we can flip the character 'O' to  a special character '#' so that we won't visit the same cell again)

### (2) Template

```java
public void BFSInMatrix(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // isStartPoint() check if we should start to search at cell (i, j)
            if (isStartPoint(matrix[i][j])) {

                Queue<Integer> queue = new LinkedList<>();

                // We can add self-defined class that contains info we are looking for to the queue
                queue.add(i * n + j);

                while (!queue.isEmpty()) {
                    int size = queue.size();

                    for (int k = 0; k < size; k++) {
                        int curPoint = queue.remove();
                        int curRow = curPoint / n;
                        int curCol = curPoint % n;

                        for (int[] direction : directions) {
                            int nextRow = curRow + direction[0];
                            int nextCol = curCol + direction[1];

                            // isValid() checks if we should search in cell (nextRow, nextCol) 
                            // given the constraint
                            if (isValid(nextRow, nextCol, matrix)) {
                                queue.add(nextRow * n + nextCol);
                            }
                        }
                    }
                }
            }
        }
    }
}
```

## 3. Time & Space Complexity

Time: O(V) , where V is the number of nodes in the graph

Space: O(V)

## 4. Questions Category

* Graph: [Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/?tab=Description\),%20%20\[Number%20of%20Connected%20Components%20in%20an%20Undirected%20Graph]\(https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/?tab=Description\),%20\[Clone%20Graph]\(https://leetcode.com/problems/clone-graph/?tab=Description\),%20\[Course%20Schedule,%20]\(https://leetcode.com/problems/course-schedule/?tab=Description\)\[Course%20Schedule%20II]\(https://leetcode.com/problems/course-schedule-ii/?tab=Description\),%20%20\[Minimum%20Height%20Trees]\(https://leetcode.com/problems/minimum-height-trees/?tab=Description)
* Matrix: [Surrounded Regions](https://leetcode.com/problems/surrounded-regions/?tab=Description), [Shortest Distance from All Buildings](https://leetcode.com/problems/shortest-distance-from-all-buildings/?tab=Description\),%20\[Number%20of%20Islands]\(https://leetcode.com/problems/number-of-islands/?tab=Description\),%20\[Walls%20and%20Gates]\(https://leetcode.com/problems/walls-and-gates/?tab=Description\),%20\[Pacific%20Atlantic%20Water%20Flow]\(https://leetcode.com/problems/pacific-atlantic-water-flow/?tab=Description\),%20\[The%20Maze]\(https://leetcode.com/problems/the-maze/?tab=Description\),%20\[The%20Maze%20II]\(https://leetcode.com/problems/the-maze-ii/?tab=Description)
* Others: [Perfect Squares](https://leetcode.com/problems/perfect-squares/?tab=Description), [Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/?tab=Description)