One of the earliest published descriptions of whatever-first search as a generic class of algorithms was by Edsger Dijkstra, Leslie Lamport, Alain Martin, Carel Scholten, and Elisabeth Steffens in 1975, as part of the design of an automatic garbage collector. Instead of maintaining marked and unmarked vertices, their algorithm maintains a color for each vertex, which is either white, gray, or black. As usual, in the following algorithm, we imagine a fixed underlying graph G.

(a) Prove that ThreeColorSearch maintains the following invariant at all times: No black vertex is a neighbor of a white vertex. [Hint: This should be easy.]

(b) Prove that after ThreeColorSearch(s) terminates, all vertices reachable from s are black, all vertices not reachable from s are white, and that the parent edges vparent(v) define a rooted spanning tree of the component containing s. [Hint: Intuitively, black nodes are “marked” and gray nodes are “in the bag”. Unlike our formulation of WhateverFirstSearch, however, the three-color algorithm is not required to process all edges out of a node at the same time.]

(c) Prove that the following variant of ThreeColorSearch, which maintains the set of gray vertices in a standard stack, is equivalent to depth-first search. [Hint: The order of the last two lines of ThreeColorStackStep matters!]

Explain your answers.
 
 

THREECOLORSEARCH(S): color all nodes white color s gray while at least one vertex is gray THREE COLORSTEP() THREECOLORSTEP(): vany gray vertex if v has no white neighbors color y black else wany white neighbor of v parent(w) + v color w gray