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.
 
 

Transcribed Image Text:

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 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

Answer rating: 100% (QA)

a Proof of Invariant Initially all vertices are colored white When a vertex s is selected and colored gray all its neighbors are either white or gray ... View the full answer