广度优先搜索例子
时间: 2023-06-21 22:15:42 浏览: 72
假设我们有一个无向图,其中节点用字母表示,边用数字表示,如下图所示:
```
A -- 1 -- B -- 2 -- C
| | |
4 5 3
| | |
D -- 6 -- E -- 7 -- F
```
我们现在要从节点 A 开始进行广度优先搜索(BFS),找到与 A 相连的所有节点,并按照字母顺序输出它们。BFS 的基本思路是从起点开始,一层一层地遍历图中的节点,直到找到目标节点或者遍历完整个图。具体实现可以用队列来完成。
按照 BFS 的算法流程,我们首先将起点 A 加入队列,然后取出队列中的第一个节点 A,找到所有与 A 相邻的节点并加入队列,即 B 和 D。由于我们要按照字母顺序输出节点,因此加入队列时需要按照字母顺序排列。此时队列中的节点为 B 和 D。接下来,我们取出队列中的第一个节点 B,找到所有与 B 相邻的节点并加入队列,即 A、C 和 E。由于 A 已经在队列中了,因此不需要重复加入。此时队列中的节点为 D、E 和 C。接下来,我们取出队列中的第一个节点 D,找到所有与 D 相邻的节点并加入队列,即 A 和 E。由于 A 和 E 已经在队列中了,因此不需要重复加入。此时队列中的节点为 E 和 C。接下来,我们取出队列中的第一个节点 E,找到所有与 E 相邻的节点并加入队列,即 B、D 和 F。由于 B 和 D 已经在队列中了,因此只需要将 F 加入队列。此时队列中的节点为 C 和 F。接下来,我们取出队列中的第一个节点 C,找到所有与 C 相邻的节点并加入队列,即 B。由于 B 已经在队列中了,因此不需要重复加入。此时队列中的节点为 F。最后,我们取出队列中的第一个节点 F,找到所有与 F 相邻的节点并加入队列,即 E。由于 E 已经在队列中了,因此不需要重复加入。此时队列已经为空,BFS 的过程结束。
按照 BFS 的遍历顺序,我们依次遍历到的节点为 A、B、D、C、E、F,因此输出结果为 A、B、C、D、E、F。