algorithm - BFS 算法 Introduction to algorithms book by cormen,leiserson etal

Question

在书中，为了解释 BFS 算法，他们假设每个顶点都可以具有三种颜色之一:白色、灰色和黑色。白色表示尚未访问过的顶点，灰色表示已访问过但可能有一些相邻顶点尚未访问过的顶点，黑色表示所有相邻顶点都已访问过的顶点。我不明白他们为什么使用三种颜色。我们甚至可以使用 2 种颜色来制作 BFS 算法:1 种颜色用于已访问的顶点，1 种颜色用于未访问的顶点。为什么我们需要第三种颜色。解决什么目的

Answer 1

基本 BFS 不需要 3 种颜色，但灰色和黑色节点之间的区别在教学上很有用，因为灰色节点仍在队列中，黑色节点已完成。