广度优先搜索★★

BFS

解决哪类问题

:::success 在树/图中搜索 :::

代码模板

如果不需要确定当前遍历到了哪一层

Deque<Node> queue = new ArrayDeque<>();
queue.push(root);
while(!queue.isEmpty()) {
    Node cur = queue.pop(); // 从栈中取出
    for node in cur.children { // 获取所有邻接节点
        if (node.isValid() && !isVisit(node)) { // 该节点有效且未访问
            queue.push(node); // 放入堆栈
        }
    }
}

如果要确定当前遍历到了哪一层

level表示二叉树遍历到哪一层或者图走了几步、size表示在当前层有多少个元素

Deque<Node> queue = new ArrayDeque<>();
queue.push(root)
int level = 0
while(!queue.isEmpty()) {
    int size = queue.size();
    while (size--) {
        Node cur = queue.pop(); // 从栈中取出
        for node in cur.children { // 获取所有邻接节点
            if (node.isValid() && !isVisit(node)) { // 该节点有效且未访问
                queue.push(node); // 放入堆栈
            }
        }
    }
    level++;
}

复杂度

O(所有节点的规模)

运用思想

递归、迭代、枚举、贪心、回溯、剪枝

例题

树

图