文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

LeetCode中广度优先搜索算法的示例分析

2023-06-19 10:29

关注

小编给大家分享一下LeetCode中广度优先搜索算法的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

一、认识广度优先搜索算法

广度优先搜索(BFS)算法是图的一种遍历方法,它的核心思想是从图的某一个节点开始,依次遍历相邻节点,再从这些相邻节点继续向外层节点遍历,直到连通图的所有节点均被访问到。

LeetCode中广度优先搜索算法的示例分析

如上图所示,A、B、C、D、E、F六个节点构成了连通图。我们使用广度优先搜索算法对该连通图进行遍历,从A点出发,找到A点的相邻节点B点和F点,再分别找到B点和F点的相邻节点C点和E点,最终找到C点和E点的共同相邻节点D点。因此我们得到的遍历结果为ABFCED。

 

二、Leetcode常见广度优先搜索形式

当我们打开Leetcode的广度优先搜索标签,查看相关算法题时会发现,很多题是将连通图简化为树或二叉树的形式展示。因此我们可以从树/二叉树的角度分析广度优先搜索算法,只要搞懂了树的广度优先搜索,图的广度优先搜索只是相邻节点的选择差异罢了。
广度优先搜索算法在树/二叉树中被简化为层次遍历算法,即从树的根节点出发,依次遍历根节点的孩子,再分别将这些孩子作为根节点,循环上述操作,直至将所有的节点全部遍历结束。
如下图所示,树的层次遍历就是一种特殊的广度优先搜索。根据上文的遍历规则不难得出树的广度优先搜索序列为ABCDEFG。

LeetCode中广度优先搜索算法的示例分析

 

三、一道算法题讲解具体的BFS实现思路

我选取了Leetcode上一道典型的广度优先搜索算法给大家整理一下BFS的算法基本实现思路,题目如下:

LeetCode中广度优先搜索算法的示例分析

思路: 从题意中我们不难看出,该题的核心问题就是求出二叉树的每一层中最右边的节点的值并将其存入数组最后返回该数组。很显然,利用广度优先搜索算法可以很容易将每一层的最右节点求出。
对于广度优先搜索算法,我们需要申请一个辅助队列帮助我们存储每一层的每一个节点。首先需要对根节点判空,若根节点为空则直接返回一个空数组,否则将根节点存入队列中。接下来我们需要将队列中该层的所有节点取出,并找出它们的孩子节点存入队列中。需要注意的是,到了最右节点时应将该节点的值存入数组。循环该过程直至遍历二叉树的所有节点即可得出最终的结果。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            TreeNode currentNode = null;
            while (count > 0) {
                count--;
                currentNode = queue.poll();
                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
            ans.add(currentNode.val);
        }
        return ans;
    }
}
 

算法复杂度分析:算法需要访问该二叉树中的每个节点并且每个节点的访问时间为O(1),所以最终的事件复杂度为O(n)。对于空间复杂度,我们申请了一个辅助队列帮助存储二叉树节点,最终的空间复杂度也可表示为O(n)。

以上是“LeetCode中广度优先搜索算法的示例分析”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯