CODEWITHSUNDEEP
algorithmdata-structuresgraph
Programmer
Programmer

Reputation: 6753

BFS algorithm Introduction to algorithms book by cormen,leiserson etal

In the book, to explain the BFS algo, they assume that each vertex can have one of the three colors: white, gray, and black. White is for vertices that have not yet been visited, gray for vertices that have been visited but may have some adjacent vertices that have not been visited, and black for vertices whose all adjacent vertices have been visited. I do not understand why they use three colors. We can make a BFS algo even with 2 colors: 1 for visited vertices and 1 color for unvisited vertices. Why do we need the third color. What purpose does it solve

Upvotes: 3

Views: 2410

Answers (3)

George Co
George Co

Reputation: 1022

The third edition (2009) of the book has a footnote saying 2 colors suffice and that exercise 22.2-3 shows this. The footnote claims that having gray and black colors helps understanding. However your question and the existence of the footnote shows to me, that at least for some of us, the extra color distracts from trying to understand the algorithm.

Upvotes: 2

Sonny Saluja
Sonny Saluja

Reputation: 7287

Theoretically, you can implement BFS with only 2 states. There are some cases where having 3 states is useful. Two of them below:

Having three states for vertices (3 colors) is useful when computing the BFS tree. Any edge from a Discovered (D) node to an Undiscovered (U) node is a tree-edge. Any edge from a discovered node to a Processed (P) node is a back edge. Any edge from a discovered node to a discovered node is a cross edge.

As another example, lets assume you were writing a program to print out all the edges of an undirected graph. With 3 colors (U, D, P) you will process all edges that go from D to U (you are discovering a new vertex) and from D to D (you are discovering an edge between siblings). However, you will not process any edge from D to P. As this will be an edge that BFS used to discover the node at D. With 2 colors, you will not be able to write such a program without duplicating certain edges.

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}

Upvotes: 0

Keith Randall
Keith Randall

Reputation: 23265

You don't need 3 colors for a basic BFS, but the distinction between grey and black nodes is useful pedagogically because the grey nodes are still in the queue and the black nodes are done.

Upvotes: 2

Related Questions