2025年广度优先搜索序列怎么做（广度优先搜索序列怎么做的）

科技前沿 • 2025-05-13 22:49 • 阅读 39

大家好，我是讯享网，很高兴认识大家。

 <p id="main-toc"><strong>目录</strong></p>

一、通过迷宫问题总结广度优先搜索算法

1、广度优先搜索的一般过程

2、广度优先搜索的特点

二、例题分析

1、员工的重要性

2、N叉树的层序遍历

3、腐烂的橘子

4、单词接龙

5、最小基因变化

6、打开转盘锁

假设有一个迷宫，用二维矩阵表示，矩阵中标记为0的地方表示可以通过，标记为1的地方表示有障碍物不能通过。现在给定迷宫大小为10*10，入口位置在(1,1)位置出口在(8,10)位置，判断从入口进来，是否可以走出迷宫，每次可以任意方向走。

尝试深度优先搜索是否可以解决：

讯享网

广度优先该如何解决这个问题呢？

观察上面两种方法，它们有什么区别？

讯享网

思路：将一个员工的所有直系下属的重要性之和计算完，在计算它们的下属的下属。即，定义一个队里用广度优先搜索的思路进行计算，首先将id元素找到并入队，队头元素出队前先将其直系下属带入队列。

思路：层序遍历，需要注意的是这里要求一层一层的输出。因此，层序遍历时还要记录当前层节点的个数和下一层的节点个数。

讯享网

这个题需要注意的是，刚开始可能就有多个橘子腐烂，所以开始时队列中可能会有多个节点。同时，每个节点带入的新节点的num应该是在该节点的基础上+1的。还有一点就是，如果没有橘子输出的结果是0.

思路：为了查找快速，建立unorder_map将字符串序列保存，并且记录该字符串是否访问过。用26个英文小写字符替换单词中的每一个字母，并且查找替换后会不会出现序列中相同的单词，如果出现则保存在队列中。直到找到endWord

讯享网

注意：和上一个题是同类型，思路完全相同

思路：对锁中的每一个+1或-1，并将结构保存在set中用于下次判断是否已经使用过。对队列进行遍历，直到找到target.需要注意的是，存在两种特殊情况“0000”就是死锁或者是target，因此需要对这两种情况进行单独判断。

讯享网