Consider the above DirectedDFS algorithm 13.11. It does not distinguish between forward and cross edges. 

a. Modify this algorithm to differentiate between these edges; that is, give its pseudocode. Thus, edges can be one of four types: tree, back, cross, or forward.

b. Give an example of running your algorithm. 

c. Prove its correctness for labeling these four edges and its running time.

 

Algorithm DirectedDFS (G, v): Label v as active // Every vertex is initially unexplored for each outgoing edge, e, that is incident to v in G do if e is unexplored then Let w be the destination vertex for e if wis unexplored and not active then Label e as a discovery edge DirectedDFS (G, w) else if w is active then Label e as a back edge else Label e as a forward/cross edge Labelu as explored Algorithm 13.11: A recursive description of the Directed DFS algorithm for search- ing from a vertex, v. Algorithm DirectedDFS (G, v): Label v as active // Every vertex is initially unexplored for each outgoing edge, e, that is incident to v in G do if e is unexplored then Let w be the destination vertex for e if wis unexplored and not active then Label e as a discovery edge DirectedDFS (G, w) else if w is active then Label e as a back edge else Label e as a forward/cross edge Label u as explored Algorithm 13.11: A recursive description of the Directed DFS algorithm for search- ing from a vertex, v.