Question
Refer to the Cormen handout of graph breadth-first search that we reviewed in class to answer these questions. During the progress of the search, vertices receive different colorings. For example (with different colors), perhaps the algorithm could end with some vertices green, some red, and some never colored. Give two different coloring configurations that could exist at the end of a search, and explain why it would end that way; be sure to include whether you are discussing a failed search or a successful one. You do not need to give a specific graph, but should probably trace some to be sure your result is possible. If only one final color configuration is possible, explain why. Do not consider graphs with no edges or no vertices. How will the algorithm behave if the search value appears more than once? Will the algorithm work with a disconnected graph? Why or why not? State the space cost of the algorithm: how much additional space is needed (beyond the original graph), and what is it used for? Does it increase as |V| increases (|V| is the size of the set of vertices), or is it fixed? Explain. The following pseudocode is the basic depth-first search algorithm. The input graph G may be undirected or directed. The variable time is a global variable that we use for timestamping. The progress of the depth-first-search algorithm DFS on a directed graph. As edges are explorered by the algorithm, they are shown as either shaded (if they are tree edges) or dahed (otherwise). Nontree edges are labeled B, C, or F according to whether they are back, cross, of forward edges. Vertices are timestamped by discovery time/finishing time. Procedure Dfs works follows Lines 1-3 paint all vertices white and initialize their pi fields to NIL. Line 4 resets the global time counter. Lines 5-7 check each vertex in V in turn and, when a white vertex is found, visit it using DFS-VISIT. Every time DFS-VISIT(u) is called in line 7, vertex u becomes the root of a new tree in the depth-first forest. When DFS returns, every vertex u has been assigned a discovery time [u] and a finishing time f[u].
Explanation / Answer
http://www.designofapproxalgs.com/book.pdf