目录

广度优先搜索 BFS

Ynthm Wang 收录于 Algorithm

2022-05-16 约 571 字预计阅读 2 分钟

目录

广度优先搜索算法（英语：Breadth-First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

平均时间复杂度 $O(|V|+|E|) = O(b^d)$
最坏时间复杂度 $O(|V|+|E|) = O(b^d)$
空间复杂度 ${\displaystyle O(|V|)=O(b^{d})}$
最佳解是
完全性是
其中 $|V|$ 是节点的数目，而 $|E|$ 是图中边的数目

DFS 是二叉树的先序遍历，BFS 对应的就是树的层序遍历，一层一层的往下遍历

BFS 递归。可以想想二叉树中如何递归的进行层序遍历。
BFS 非递归。一般用队列存储。
DFS 递归。最常用，如二叉树的先序遍历。
DFS 非递归。一般用 stack。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> list = new ArrayList<>();
        // 完整的一个循环即表示一层
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            list.add(cur.val);
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        res.add(list);
    }
    return res;
}

应用

广度优先搜索算法能用来解决图论中的许多问题，例如：

查找图中所有连接组件（Connected Component）。一个连接组件是图中的最大相连子图。
查找连接组件中的所有节点。
查找非加权图中任两点的最短路径。
测试一图是否为二分图。
（Reverse）Cuthill–McKee算法

https://zh.wikipedia.org/zh-cn/广度优先搜索