起点为3, 终点为5, 利用广度优先搜索的步骤如下:
- 分层, 起点是第0层
- 从起点最少需 n 步就能到达的点就属于第 n 层
如上图的例子:
- 第零层:
3 - 第一层:
2,4,6 - 第二层:
1,5 - 第三层:
0
搜索的过程也是各个节点扩展的过程. 以上图为例:
- 起点
3能扩展出2,4,6. 2能扩展出1, 但不能扩展出4(因为4已经被起点扩展出来了)4能扩展出5,6不能扩展出5(已经被4扩展出了)1能扩展出0
所有搜索序列是: 3, 2, 4, 6, 1, 5
广度搜索的算法一般是创建两个队列, 一个放已经访问过的节点, 另一个放被扩展出的节点.
以上图为例, 从起点3到终点5的搜索过程如下:
将起点3放入open队列.
起点3出队, 进入close队列.
与此同时, 3扩展出的2, 4, 6进入open队列.
节点2出队, 进入close队列.
被2扩展出的1进入open队列.
节点4出队, 进入close队列.
与此同时, 被4扩展出的5进入open队列.
节点6出队, 进入close队列.
由于6能扩展出5, 而5已经被4扩展出了, 所有这里不做过多操作.
节点1出队, 进入close队列.
与此同时, 被1扩展出的0进入open队列.
节点5出队, 进入close队列.
由于5就是我们的终点, 所以搜索过程结束.
若有收获，就点个赞吧
0 人点赞
