小工具知识网

当前位置: 首页 > 行业知识 > 宽度优先搜索算法(BFS)

行业知识

宽度优先搜索算法(BFS)

2026-11-16 10:23:31 来源:互联网转载

宽度优先搜索算法(BFS)是什么?

宽度优先���索算法(BFS)(也称为广度优先搜索)主要运用于树、图和矩阵(这三种可以都归类在图中),用于在图中从起始顶点开始逐层地向外探索,直到找到目标顶点为止。

在本篇文章中,我们主要讨论其在树中的运用

树的宽度优先搜索

树的宽度优先搜索 即 树的层序遍历 :逐层访问树的节点,并按照层级顺序输出节点的值。从树的根节点开始,逐层向下遍历,先访问当前层的所有节点,然后再访问下一层的节点,依次类推直到遍历完整棵树

其过程如下图所示:

如何实现树的层序遍历呢?

我们在遍历每一层节点时,都是从左向右依次遍历的,即先遍历上一层节点中的第一个节点的孩子节点 ,即优先遍历前面的节点,此时,满足 “先进先出”,因此,我们可以使用队列来帮助我们完成层序遍历

具体步骤如下:

1. 先将根节点放入队列中

2. 从队列中出队一个节点,并将该节点的所有孩子节点(如果有)依次放入队列中

3. 继续取出节点,指导队列为空

4. 当队列为空时,遍历完成

接下来,我们通过一些练习来进一步体会和掌握BFS

相关练习

练习1:N叉树的层序遍历

题目链接:

429. N 叉树的层序遍历 - 力扣(LeetCode)

题目描述:

给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。

树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。

示例 1:

输入:root = [1,null,3,2,4,null,5,6]输出:[[1],[3,2,4],[5,6]]

示例 2:

输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示:

  • 树的高度不会超过 1000
  • 树的节点总数在 [0, 10^4] 之间

    思路分析:

     本题要求我们返回N叉树节点值的层序遍历,且以 List类型的结果返回,即每一层使用一个列表来存储本层的所有节点的值,然后将这些列表放到一个列表中返回

    在这里,我们可以使用队列来帮助我们进行层序遍历,但在将节点出队时,也会将其孩子节点放入队列中,那么,我们如何区分每一层的节点呢?

     我们可以使用一个变量 count 在节点出队之前,记录队列当前节点个数(即这一层节点个数),然后再将这 count 个节点依次出队列,将其节点值放入列表中,同时将其孩子节点放入队列中

    具体步骤:

    1. 先判断树是否为空,不为空将根节点放入队列中

    2. 记录当前队列中包含的节点个数count

    3. 将count个节点依次出队列,将其节点值放入一个临时列表中,同时将其孩子节点放入队列中

    4. 遍历完count个节点后,临时列表中就存放了这一层所有节点的值,然后再将临时列表放入结果列表中

    5. 继续遍历,直到队列为空

    6. 返回结果

    代码实现:

    class Solution {    public List levelOrder(Node root) {       List ret = new ArrayList();        Node cur = root;        Queue queue = new ArrayDeque();        //先将根节点放入队列中        if(cur == null) return ret;        queue.add(cur);        int count = 0;        while (!queue.isEmpty()){            //先记录当前队列中节点个数            count = queue.size();            List tmp = new ArrayList();//使用临时表存储这一层节点的值            for (int i = 0; i  

    练习2:二叉树的锯齿形层序遍历

    题目链接:

    103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode)

    题目描述:

    给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

    示例 1:

    输入:root = [3,9,20,null,null,15,7]输出:[[3],[20,9],[15,7]]

    示例 2:

    输入:root = [1]输出:[[1]]

    示例 3:

    输入:root = []输出:[]

    提示:

    • 树中节点数目在范围 [0, 2000] 内
    • -100

上一篇:原神账户怎么还服务器?

下一篇:要怎么ping远处服务器?