广度优先搜索(BSF)的理解
广度优先搜索方法的实现
(基于《学习JavaScript数据结构与算法》补充学习)
实现步骤如下
- 1.用
initializeColor
函数来将color
数组初始化为白色;也就是将每个节点初始化为白色未读 - 2.声明和创建一个队列Queue实例,用于储存 待访问 和 待探索的顶点
- 3.将我们的起始的顶点加入队列
- 4.然后我们就进入循环,循环的条件是队列不为空
- (1)循环第一步:我们从队列中移除一个顶点,并通过邻接表
adjList
来获取该顶点的所有邻居,并将该顶点color置为灰色表示该顶点已被我们发现 - (2)循环第二步:在获取了上一步我们的顶点的邻居后,我们开始对这些邻居做个for循环,在for循环中我们会判断这些邻居是否为white即是否曾被发现过,如果是white我们就将其置为grey即被我们发现了,并且我们还要将这些邻居放入我们的队列
- (3)循环第三步:将该顶点的color置为black,表示经过以上两步表示我们对该顶点已经完成探索了
- (4)继续循环:因为我们上一步将我们顶点的邻居放进了队列,因此我们在这个循环中会依据队列先进先出的原则根据之前的邻接表来继续我们的循环,
补充一下:我们的BFS 和DFS 的区别就在这里了,我们采用队列还是栈将会决定我们的邻居被探索的顺序
- (1)循环第一步:我们从队列中移除一个顶点,并通过邻接表