连通图(分量)的BFS算法
算法实现讨论
- 与DFS类似,同样要设访问标志数组visited[ ]。
- 为了能依次访问上一层次的访问序列中的各顶点的邻接点,需要设置一个结构來保存上一层次的顶
点,即刚刚被访问过且其后继邻接点还未被访问的顶点,并且这一结构还要满足这样的条件:这一
层中最先被访问的顶点,其后继邻接点也应被最先访问到。由此可知,这一结构应是==队列==。 - 既然涉及到队列(不妨设为Q),则需要在适当的情况下操作队列:
(a)初始化:开始时要设置队列Q为空;
(b)入队:每访问一个顶点v,除了访问操作、设置标志外,还要将其入队。在此不妨设为enQueue(v)。
(c)出队:取队头元素v,不妨用getFront(v),队头出队,然后要依次访问v的所有未被访问过的邻接点。求解v的邻接点,方法与DFS相同。 - 综上所述,可将BFS(v)细化如下:
- 初始化队列Q;
- 访问v(包括三个操作:访问v,设置标志,入队)
- 若队列Q为空,则结束BFS(v),否则,转4
- v=Q.getFront(Q); Q.oueQueue()
- w=v的第一邻接点 //依次访问v的未被访问的邻接点
- 若w未被访问过,则访问w(同样包括访问w,设置标志,入队这三个操作)
- w=v的下一个邻接点,若不存在,转3
- 转6
BFS算法描述
1 | // An highlighted block |
一般图的(通用)BFS算法
算法描述
1 | // An highlighted block |
连通图(分量)BFS的实现
(1) BFS基于邻接矩阵的实现参考
1 | // An highlighted block |
(2)BFS基于邻接表的实现参考
1 | // An highlighted block |