discuz网站建设教学视频,2021年网络营销考试题及答案,软件职业培训,怎么创建一个网页今天我们来学习一下一个新的搜索#xff0c;广度优先搜索。 1.广度优先搜索的前提 队列#xff08;queue#xff09; 是一种 操作受限制 的线性表#xff0c;其限制#xff1a; 只允许从表的前端#xff08;front#xff09;进行删除操作#xff1b; 只允许在表的后端…
今天我们来学习一下一个新的搜索广度优先搜索。 1.广度优先搜索的前提 队列queue 是一种 操作受限制 的线性表其限制 只允许从表的前端front进行删除操作 只允许在表的后端rear进行插入操作。
一般允许进行插入的一端我们称为 队尾 允许删除的一端称为 队首 队列的主要操作包括 入队push队列的插入操作 出队pop队列的删除操作 判断队列是否为空empty 统计队列元素的个数size 访问队首元素front
数据存取特点具有 先进先出 的性质。 2.广度优先搜索 广度优先搜索又称宽度优先搜索简称 BFS我们以后都会用 BFS 来表示广度优先搜索。与深度优先搜索不同的是广度优先搜索会先将与起始点距离较近的点搜索完毕再继续搜索较远的点而深搜却是沿着一个分支搜到最后。
BFS 从起点开始优先搜索离起点最近的点然后由这个最近的点扩展其他稍近的点这样一层一层的扩展就像水波扩散一样。 对上图进行深搜按照顶点访问顺序会得到序列A−B−E−F−C−D−G
对上图进行广搜按照顶点访问顺序会得到序列A−B−C−D−E−F−G
广度优先搜索的层次关系是很明显的上面的图的分层次关系如下 第一层的点为 A 第二层的点为 B,C,D 第三层的点为 E,F,G BFS 需要借助队列来实现 初始的时候把起始点放到队列中并标记起点访问。 如果队列不为空从队列中取出一个元素 x否则算法结束。 访问和 x 相连的所有点 v如果 v 没有被访问把 v 入队并标记已经访问。 重复执行步骤 2。 最后写出来的代码框架如下
void bfs(起始点) {/*将起始点放入队列中;*//*标记起点访问;*/while (/*如果队列不为空*/) {/* 访问队列中队首元素x *//* 删除队首元素 */for (/* x 所有相邻点 */) {if (/* 该点未被访问过且合法 */) {/*标记该点访问*//*将该点加入队列末尾*/}}}/*队列为空广搜结束*/
}
注意这里标记一个点是否访问必须在放入队列的时候标记避免一个点在队列中但没被访问的情况下再次被放入队列的可能。
