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

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

• 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, (Here, we can flip the character 'O' to a special character '#' so that we won't visit the same cell again)

(2) Template

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

• Matrix: Surrounded Regions, Shortest Distance from All Buildings

• Others: Perfect Squares, Remove Invalid Parentheses