Algorithm BFS Introduction to the book of algorithms cormen, leiserson etal

Question

In the book, to explain BFS algo, they suggest that each vertex can have one of three colors: white, gray, and black. White - for peaks that have not been visited, gray for peaks visited, but can have neighboring peaks that have not been visited, and black for peaks, all visited neighboring peaks. I do not understand why they use three colors. We can make BFS algo even with two colors: 1 for visited vertices and 1 color for invisible vertices. Why do we need a third color. What goal does he decide?

Answer 1

You do not need 3 colors for the underlying BFS, but the distinction between gray and black nodes is pedagogically useful because the gray nodes are still in the queue and the black nodes are done.

Answer 2

In the third edition (2009) of the book, there is a footnote in which 2 colors are indicated, and this exercise 22.2-3 shows this. The footnote states that the presence of gray and black colors helps to understand. However, your question and the presence of a footnote show me that, at least for some of us, the complementary color distracts from trying to understand the algorithm.

Answer 3

BFS . , 3 . :

BFS (3 ). (D) node Undiscovered (U) node . node (P) node . node node .

, . 3 (U, D, P) , D U ( ) D D ( ). , D P. , BFS node D. 2 ​​, .

1----2
|    |
|    |
3----4

BFS starting at 1:
Tree Edges: {1, 2}, {1, 3}, {3, 4}
Cross Edge: {2, 4}

Without three states you will try to process {2, 1}, {3, 1}, {4, 3}, {4, 2}