BFS
应用场景
一般用来解决最短连通路径问题。
基本思路
单源BFS：借助Queue，将源点存进Queue，然后每次从Queue的头取一个元素，将所有 unvisited neighbors加到Queue尾，依次进行，直到Queue空。
Typical BFS 写法
Queue q;
Set visited;
q.add(node);
while(q is not empty) {
Node cur = q.poll();
for(Node neighbor: cur.neighbors) {
if(neighbor is not visited) {
q.add(neighbor);
}
}
}经典题目
323 Number of Connected Components in an Undirected Graph
// time: O(V + E + V * E) ???
public int countComponents(int n, int[][] edges) {
List<List<Integer>> graph = buildGraph(n, edges);
int ans = 0;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
Deque<Integer> queue = new LinkedList<>();
queue.offerLast(i);
while (!queue.isEmpty()) {
int cur = queue.pollFirst();
visited[cur] = true;
List<Integer> list = graph.get(cur);
if (list != null) {
for (Integer nei : list) {
if (!visited[nei]) {
queue.offerLast(nei);
}
}
}
}
ans += 1;
}
}
return ans;
}
private List<List<Integer>> buildGraph(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<Integer>());
}
for (int[] edge: edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
return graph;
}class Solution {
private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public void wallsAndGates(int[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
int n = rooms.length;
int m = rooms[0].length;
Deque<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (rooms[i][j] == 0) {
//bfs(i, j, n, m, rooms);
queue.offerLast(new int[] {i, j});
visited[i][j] = true;
}
}
}
bfs(n, m, queue, visited, rooms);
}
private void bfs(int n, int m, Deque<int[]> queue, boolean[][] visited, int[][] rooms) {
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while(size-- > 0) {
int[] cur = queue.pollFirst();
for (int i = 0; i < dirs.length; i++) {
int nextRow = cur[0] + dirs[i][0];
int nextCol = cur[1] + dirs[i][1];
if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m && !visited[nextRow][nextCol] && rooms[nextRow][nextCol] > 0) {
visited[nextRow][nextCol] = true;
queue.offerLast(new int[] {nextRow, nextCol});
}
}
rooms[cur[0]][cur[1]] = step;
}
step++;
}
}
}675. Cut Off Trees for Golf Event
// 有几个陷阱要注意：1. (0, 0)是需要进栈的，因为有可能不是先砍(0, 0)
// 2. 如果(0, 0)点是最小点，则直接砍，也就是说BFS的时候，得预先判断一下。
// 3. BFS的时候，判断neighbor是不是valid，只需要看能不能走就行。
class Solution {
private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int cutOffTree(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList<>();
for (int i = 0; i < forest.size(); i++) {
List<Integer> row = forest.get(i);
for (int j = 0; j < row.size(); j++) {
int val = row.get(j);
if (val > 1) {
trees.add(new int[] {i, j, val});
}
}
}
Collections.sort(trees, (int[] a, int[] b) -> (a[2] - b[2]));
int sr = 0, sc = 0;
int ans = 0;
for (int[] tree: trees) {
int dist = getDistance(sr, sc, tree[0], tree[1], forest);
//System.out.println(dist);
if (dist == -1) return -1;
ans += dist;
sr = tree[0];
sc = tree[1];
}
return ans;
}
// BFS to find shortest path
private int getDistance(int sr, int sc, int dr, int dc, List<List<Integer>> forest) {
if (sr == dr && sc == dc) {
return 0;
}
int n = forest.size();
int m = forest.get(0).size();
Deque<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
queue.offerLast(new int[] {sr, sc});
visited[sr][sc] = true;
int step = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int[] cur = queue.pollFirst();
for (int i = 0; i < dirs.length; i++) {
int nextRow = cur[0] + dirs[i][0];
int nextCol = cur[1] + dirs[i][1];
if (nextRow == dr && nextCol == dc) {
return step;
}
if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m && !visited[nextRow][nextCol] && forest.get(nextRow).get(nextCol) > 0) {
visited[nextRow][nextCol] = true;
queue.offerLast(new int[] {nextRow, nextCol});
}
}
}
step++;
}
return -1;
}
}863. All Nodes Distance K in Binary Tree
// 类似于 KNN，以 target 为中心，做BFS
class Solution {
class MyNode {
int val;
MyNode left, right, parent;
public MyNode(int x) {
val = x;
}
}
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> ans = new ArrayList<>();
// Rebuild a binary tree with the parent property
MyNode[] array = new MyNode[] {null};
MyNode myNode = rebuild(root, null, target, array);
// New Target Node
MyNode targetNode = array[0];
// Start from New Target Node, do BFS
// Stop at distance K
Deque<MyNode> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offerLast(targetNode);
visited.add(targetNode.val);
while (K-- > 0) {
int size = queue.size();
while (size-- > 0) {
MyNode cur = queue.pollFirst();
if (cur.left != null && !visited.contains(cur.left.val)) {
visited.add(cur.left.val);
queue.offerLast(cur.left);
}
if (cur.right != null && !visited.contains(cur.right.val)) {
visited.add(cur.right.val);
queue.offerLast(cur.right);
}
if (cur.parent != null && !visited.contains(cur.parent.val)) {
visited.add(cur.parent.val);
queue.offerLast(cur.parent);
}
}
}
// Remaining Nodes in queue are all distance K from New Target Node
while (!queue.isEmpty()) {
ans.add(queue.pollFirst().val);
}
return ans;
}
private MyNode rebuild(TreeNode node, MyNode parent, TreeNode target, MyNode[] array) {
if (node == null) return null;
MyNode myNode = new MyNode(node.val);
myNode.left = rebuild(node.left, myNode, target, array);
myNode.right = rebuild(node.right, myNode, target, array);
myNode.parent = parent;
if (target.val == node.val) {
array[0] = myNode;
}
return myNode;
}
}Last updated