广度优先搜索 队列（广度优先搜索算法代码）



图是一种常见的数据格式，它的遍历主要分为两种： 深度优先遍历(DFS)：类似于二叉树的前序前序遍历 广度优先遍历(BFS)：类似于二叉树的层次遍历

深度优先遍历（DFS）

定义

深度优先遍历（DFS，Depth-First Search）是一种图遍历算法，它沿着图的深度方向进行搜索。DFS 从一个起始节点开始，优先访问未被访问的邻接节点，尽可能深地探索每个分支，直到所有可能的分支都被访问过，然后回溯到上一个节点继续探索。

与二叉树遍历的类比

广度优先遍历（BFS）

定义

广度优先遍历（BFS，Breadth-First Search）是一种图遍历算法，它沿着图的广度方向进行搜索。BFS 从一个起始节点开始，逐层访问所有邻接节点，然后继续访问这些邻接节点的邻接节点，直到图中的所有节点都被访问过。

与二叉树遍历的类比

例题

图的深度优先遍历类似于二叉树的( )。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

题解

选A。图的深度优先遍历相当于 二叉树的前序遍历，因为它在访问节点时首先处理节点本身，然后递归地访问所有子节点。尽管 DFS 可以应用于任意图结构，而不仅限于树，但其遍历节点的顺序与二叉树的前序遍历最为接近。

总结

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/51723.html