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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/my-algorithm-summary/chapter1/breath-first-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.