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

(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

PreviousTopological Sorting Next694 Number of Distinct Islands

Last updated 5 years ago

Was this helpful?

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:

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: , (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);
                            }
                        }
                    }
                }
            }
        }
    }
}