Breath First Search是一种用于图数据结构的图遍历技术。它逐级进行。图是树状的数据结构。为了避免在遍历图的过程中访问节点,我们使用BFS。
在这个算法中,假设我们从节点 x 开始,然后我们将访问 x 的邻居,然后访问 x 的邻居的邻居,依此类推。
算法
为了使用BFS遍历图,我们使用队列来存储节点和数组数据结构来区分未访问的节点。
- 1 . 创建空队列并将未访问的顶点推送到它。
- 2 . 除非队列为空,否则请执行以下操作。
- 2.1从队列中弹出元素
- 2.2将弹出节点的未访问的相邻节点推入队列。
考虑这张图
根据[……]