概述
- 从根开始(图则选择一些任意节点作为根)并且在移动到下一级邻居之前首先探索邻居节点
- 以当前节点为圆心画圆，层层递进，将覆盖的节点放入队列
- 不需要递归，利用队列解决
- 图 BFS 需要涂色
场景
- 树的层序遍历
- 图搜索/遍历
- 拓扑排序
- 求最短路径
- 能用 BFS 速求的题目就不要用 DFS
二叉树 BFS 模板
import java.util.ArrayList;
public class BinaryTreeLevelOrder {
public List<List<Integer>> levelOrder(TreeNode root) {
// Ideas: BFS => queue => for loop for every level
List<List<Integer>> result = new ArrayList<>();
// check input
if (root == null) {
return result;
}
// Queue
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// number of every level
int size;
// traversal
while (!queue.isEmpty()) {
// single result of every level
List<Integer> list = new ArrayList<>();
size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(list);
}
return result;
}
}
图中 BFS
public class BFSInGraph {
public void bfsInGraph(int nodeNum, int[] edges, int[][] adjacencyMatrix) {
// check input
if (nodeNum < 1 || adjacencyMatrix == null || adjacencyMatrix.length == 0 || adjacencyMatrix[0] == null || adjacencyMatrix[0].length == 0) {
return;
}
// construct adjacencyList => Map<Node, List<Node>> => node -> adjacency node
Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
for (int i = 0; i < nodeNum; i++) {
adjacencyList.add(i, new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
adjacencyList.get(u).add(v);
adjacencyList.get(v).add(u);
}
// marked
boolean[] visited = new boolean[nodeNum];
boolean[] visited = new boolean[adjacencyMatrix.length];
int connectComponentCount = 0;
// traversal in adjacencyList
for (int node : adjacencyList.keySet()) {
if (specialCondition && !visited[node]) {
bfs(adjacencyList, adjacencyMatrix, visited, node);
connectComponentCount++;
}
}
// traversal in adjacencyMatrix
for (int i = 0; i < adjacencyMatrix.length; i++) {
if (specialCondition && !visited[i]) {
bfs(adjacencyList, adjacencyMatrix, visited, i);
connectComponentCount++;
}
}
}
private void bfs(Map<Integer, List<Integer>> adjacencyList, int[][] adjacencyMatrix, boolean[] visited, int start) {
// queue
Queue<Integer> queue = new LinkedList<>();
// offer & marked
queue.offer(start);
visited[start] = true;
// traversal in adjacencyList
while (!queue.isEmpty()) {
int node = queue.poll();
// traversal adjacency node
for (int adjacencyNode : adjacenList.get(node)) {
if (specialCondition && !visited[adjacencyNode]) {
// offer & marked
queue.offer(adjacencyNode);
visited[adjacencyNode] = true;
}
}
}
// traversal in adjacencyMatrix
while (!queue.isEmpty()) {
int node = queue.poll();
// traversal adjacency node
for (int i = 0; i < adjacencyMatrix[node].length; i++) {
if (specialCondition && !visited[i]) {
// offer & marked
queue.offer(i);
visited[i] = true;
}
}
}
}
}
二维问题 BFS
public class BFSInMatrix {
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, -1, 0, 1};
public void bfsInMatrix(int[][] matrix) {
// 时间复杂度：O(m * n)
// 空间复杂度：O(m * n)
// check input
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return;
}
// marked
int m = matrix.length;
int n = matrix[0].length;
boolean[][] visited = new boolean[m][n];
int connectComponentCount = 0;
// traversal
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (specialCondition && !visited[i][j]) {
bfs(matrix, visited, i, j);
connectComponentCount++;
}
}
}
}
public void bfs(int[][] matrix, boolean[][] visited, int x, int y) {
// queue
Queue<Point> queue = new LinkedList<>();
// offer & marked
queue.offer(new Point(x, y));
visited[x][y] = true;
// move
while (!queue.isEmpty()) {
Point point = queue.poll();
for (int i = 0; i < 4; i++) {
int newX = point.x + dx[i];
int newY = point.y + dy[i];
if (checkRange(matrix, newX, newY) && !visited[newX][newY] && specialContition) {
// offer & marked
queue.offer(new Point(newX, newY));
visited[newX][newY] = true;
}
}
}
}
private boolean checkRange(int[][] matrix, int x, int y) {
return x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length;
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
拓扑排序 Topological Sort
对于一个有向无环图(DAG)进行拓扑排序，是将 DAG 中所有顶点排成一个线性序列，使得对图中任意一条边(u, v)，u 在线性序列中出现在 v 之前。通常这样的线性序列成为满足拓扑次序(Topological Order)的序列，简称拓扑序列
- 必须是有向无环图(DAG)才有拓扑排序
- 若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B之前
- 拓扑排序通常用来排序具有依赖关系的任务
- 拓扑排序并不唯一
卡恩算法
- 遍历所有图节点，把入度为0的节点入队
- 当队列不为空时，取出一个节点 v 放入序列
- 将与 v 相邻的节点入度减1，然后把减1后入度为0的节点入队
- 重复 2，3 步，直到队列为空，返回序列即为拓扑序列
- 如果拓扑序列中节点数量少于图节点数量则说明该有向图存在环
要点
- 计算每个节点的入度，用 map 维护
- 将入度为0的节点均加入队列
- while 循环队列，取出节点
- 得到节点的邻接节点，将所有邻接节点的入度减1，并更新 map
- 若邻接节点更新后的入度为0，加入队列
实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class DirectedGraph {
private final List<DirectedGraphNode> graphNodes;
public DirectedGraph(List<DirectedGraphNode> graphNodes) {
this.graphNodes = graphNodes;
}
public List<DirectedGraphNode> topologicalSort() {
// 1. 计算每个图节点的入度，用 map 维护，key：当前图节点，value：入度值
Map<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>();
for (DirectedGraphNode node : graphNodes) {
for (DirectedGraphNode adjacencyNode : node.getAdjacencyNodes()) {
inDegreeMap.merge(adjacencyNode, 1, Integer::sum);
}
}
// 2. 将入度为 0 的节点入队
Queue<DirectedGraphNode> queue = new LinkedList<>();
for (DirectedGraphNode node : graphNodes) {
if (!inDegreeMap.containsKey(node)) {
queue.offer(node);
}
}
// 3. BFS
List<DirectedGraphNode> topologicalList = new ArrayList<>();
while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
topologicalList.add(node);
// 得到节点的邻接节点，将所有邻接节点的入度减1，并更新 map => 若邻接节点更新后的入度为0，加入队列
for (DirectedGraphNode adjacencyNode : node.getAdjacencyNodes()) {
int newInDegree = inDegreeMap.get(adjacencyNode) - 1;
inDegreeMap.put(adjacencyNode, newInDegree);
if (newInDegree == 0) {
queue.offer(adjacencyNode);
}
}
}
return topologicalList;
}
public static void main(String[] args) {
DirectedGraphNode node5 = new DirectedGraphNode(5);
DirectedGraphNode node2 = new DirectedGraphNode(2, Collections.singletonList(node5));
DirectedGraphNode node3 = new DirectedGraphNode(3, Collections.singletonList(node5));
DirectedGraphNode node6 = new DirectedGraphNode(6, Collections.singletonList(node5));
DirectedGraphNode node4 = new DirectedGraphNode(4, Arrays.asList(node5, node6));
DirectedGraphNode node1 = new DirectedGraphNode(1, Arrays.asList(node2, node3, node4));
List<DirectedGraphNode> graphNodes = Arrays.asList(node1, node2, node3, node4, node5, node6);
DirectedGraph directedGraph = new DirectedGraph(graphNodes);
List<DirectedGraphNode> directedGraphNodes = directedGraph.topologicalSort();
directedGraphNodes.forEach(node -> System.out.println(node.getNo()));
}
}
模板
public class TopologicalSort {
public List<Integer> topologicalSort(int nodeNum, int[] edges, int[][] adjacencyMatrix) {
// check input
if (nodeNum < 1 || adjacencyMatrix == null || adjacencyMatrix.length == 0 || adjacencyMatrix[0] == null || adjacencyMatrix[0].length == 0) {
return null;
}
// 1. construct adjacency list
Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
for (int i = 0; i < nodeNum; i++) {
adjacencyList.put(i, new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
adjacencyList.get(u).add(v);
adjacencyList.get(v).add(u);
}
// 2. calculate in degree -> int -> int => adjacency list
int[] inDegree = new int[nodeNum];
for (int node : adjacency.keySet()) {
inDegree[node] = adjacency.get(node).size();
}
// 2. calculate in degree -> int -> int => adjacency matrix
int[] inDegree = new int[adjacencyMatrix.length];
for (int i = 0; i < adjacencyMatrix.length; i++) {
int currentInDegree = 0;
for (int j = 0; j < adjacencyMatrix[i].length; j++) {
if (adjacencyMatrix[i][j] != 0) {
currentInDegree++;
}
}
inDegree[i] = currentInDegree;
}
// 3. in degree is zero push queue
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
// 4. BFS
List<Integer> topologicalList = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
topologicalList.add(node);
// 5. adjacency node in degree subtract 1 => adjacency list
for (int adjacencyNode : adjacencyList.get(node)) {
int newIndegree = inDegree[adjacencyNode] - 1;
inDegree[adjacencyNode] = newIndegree;
if (newIndegree == 0) {
queue.offer(adjacencyNode);
}
}
// 5. adjacency node in degree subtract 1 => adjacency matrix
for (int i = 0; i < adjacencyMatrix[node].length; i++) {
if (adjacencyMatrix[node][i] == 1) {
int newInDegree = inDegree[i] - 1;
inDegree[i] = newIndegree;
if (newIndegree == 0) {
queue.offer(i);
}
}
}
}
return topologicalList;
}
}
最短路径相关问题 BFS
- 由于 BFS 层层遍历的特点，可以解决部分最短路径问题
- 二叉树最小深度
- 走出迷宫的最短路径
双向 BFS
- 单向 BFS 的局限 => 搜索空间可能巨大
- 分别从起点和终点出发进行 BFS，看是否能够相遇
- 需要维护两个队列，用数组或哈希表记录搜索状态
- 当某个节点被两个 BFS 同时标记则搜索结束
- 尽可能让两个方向搜索平均 => Q1 > Q2 时，只移动 Q2
