算法设计题写出广度优先搜索遍历的遍历算法

1个回答

月亮弯弯hd

专业答主服务有保障

关注

展开全部

摘要 3.既然涉及到队列（不妨设为Q），则需要在适当的情况下操作队列：

（a）初始化：开始时要设置队列Q为空；

（b）入队：每访问一个顶点v，除了访问操作、设置标志外，还要将其入队。在此不妨设为enQueue(v)。

（c）出队：取队头元素v，不妨用getFront(v)，队头出队，然后要依次访问v的所有未被访问过的邻接点。求解v的邻接点，方法与DFS相同。

咨询记录 · 回答于2022-05-03

算法设计题写出广度优先搜索遍历的遍历算法

亲，您好，经查询，在百度信息上是没有这个信息的标准答案呢，为您查询到以下参考信息

BFS算法连通图（分量）的BFS算法算法实现讨论BFS算法描述一般图的（通用）BFS算法算法描述连通图（分量）BFS的实现

连通图（分量）的BFS算法算法实现讨论

1.与DFS类似，同样要设访问标志数组visited[ ]。

2.为了能依次访问上一层次的访问序列中的各顶点的邻接点，需要设置一个结构来保存上一层次的顶点，即刚刚被访问过且其后继邻接点还未被访问的顶点，并且这一结构还要满足这样的条件：这一层中最先被访问的顶点，其后继邻接点也应被最先访问到。由此可知，这一结构应是队列。

3.既然涉及到队列（不妨设为Q），则需要在适当的情况下操作队列：（a）初始化：开始时要设置队列Q为空；（b）入队：每访问一个顶点v，除了访问操作、设置标志外，还要将其入队。在此不妨设为enQueue(v)。（c）出队：取队头元素v，不妨用getFront(v)，队头出队，然后要依次访问v的所有未被访问过的邻接点。求解v的邻接点，方法与DFS相同。

4.综上所述，可将BFS(v)细化如下：初始化队列Q；访问v（包括三个操作：访问v，设置标志，入队）若队列Q为空，则结束BFS(v)，否则，转4v=Q.getFront(Q); Q.oueQueue()w=v的第一邻接点 //依次访问v的未被访问的邻接点若w未被访问过，则访问w（同样包括访问w，设置标志，入队这三个操作）w=v的下一个邻接点，若不存在，转3转6

已赞过

评论收起