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
Last updated
Was this helpful?