**P5**from Week 08 quiz questions (take home, to be done before Class 20)**P6**from Week 08 quiz questions (take home, to be done before Class 20)

The idea is this: in our previous search, a vertex was either "visited" or "unvisited", and that was it. Now we'll make three categories: unvisited, visit-in-progress, visit-complete, which we'll represent as the "colors" white, gray and black. First we'll phrase this recursively. "Depth first visit" plays the role of our search, and to complete the presentation in the same basic form as Cormen Leiserson and Rivest, we'll have a "driver" called "depth first search" that makes sure all vertices are eventually found.

Depth first visit | Depth first search |

DFSVisit(vertex u) color u gray for each neighbor v of u do if v is white DFSVisit(v) color u black | DFS(graph G) set the color of all vertices in G to white for each vertex u in G do if u is white DFSVisit(u) |

We can make DFSVisit an iterative algorithm and see that it's got the Stack connection to our original formulation to depth-first-search as follows (Note: in [ ]'s is some optional bookkeeping that can be done while the search progresses. We'll talk more about what this additional bookkeeping does for you):

DFSVisit(vertex s) initialize S to an empty stack of vertex-integer pairs color s gray [ parent[s] = null; time++; d[u] = time; ] S.push((s,1)) while S not empty do (u,k) = S.pop() if u has k or more neighbors S.push(u,k+1) v = u's kth neighbor if v's color is white color v gray [ parent[v] = u; time++; d[u] = time; ] S.push(v, 1) else color u black [ time++; f[u] = time; ]Now we get this beautiful property that the stack S is precisely the path from root s down to the current vertex u in the search tree. Moreover, since only the vertices currently on the stack are colored gray, we can check in constant time whether a given vertex is "on the current path" by checking its color.

- We still have the same concept of "search tree", and once again if we do the optional bookkeeping and keep track of the "parent" fields, that tree is explicit, i.e. we can recover it.
- The gray vertices are exactly he vertices on the stack, and the vertices on the stack, ordered from bottom to top, comprise a path, and this path is a path in the search tree.
- Consider the vertex v at line "v = u's kth neighbor". If v is colored white, then the descendents of v in the searchtree that is ultimately generated will be exactly the vertices reachable from v via paths consisting solely of vertices colored white. Moreover, all such vertices will be colored black before v gets colored black.

**Theorem:**
Suppose DFS is run on directed graph G.
G has cycles if and only if
at some point vertex v at line "v = u's kth neighbor" has
color gray.
**Proof:**
If $v$ is colored gray, then it is on the current stack, which
means that there is a path from $v$ to $u$. Because this
vertex is a "$v$" in the algorithm, there is an edge from $u$
to $v$, which completes the cycle.
More interestingly, if there is a cycle in $G$, can we show
that we must eventually have a "$v$" that's colored gray?
Denote by $w$ the first vertex encountered by DFS that is a
part of a cycle (i.e. all prior vertices encountered are not
part of any cycle). Then any cycle involving $w$ consistes
purely of vertices currently colored white. At least one such
vertex must have an edge back to $w$ (otherwise $w$ would not
be the first encountered vertex that's part of a cycle),
denote such a vertex by $y$. $y$ is colored black before $w$,
so $w$ is still gray when every one of the neighbors of $y$ is
processed, including the point at which $w$ itself is
processed as a neighbor, which means we will be at a point
where $v$ from "v = u's kth neighbor" is colored gray.