Assume this directed graph is represented using adjacency lists, but do not assume any particular ordering...

Transcribed Image Text:

Assume this directed graph is represented using adjacency lists, but do not assume any particular ordering of the arcs on the adjacency lists. (a) Find all possible depth-first search trees starting at node E. If not all nodes are included in a single tree, determine the remaining trees in the forest starting at unvisited nodes in alphabetical order. For each depth-first search tree/forest, label nodes with their postorder numbers. (b) If the adjacency lists are ordered alphabetically based on the node names (i.e., A comes first and F last), which of the depth- first search trees from part (a) will be generated? (c) Starting at node A, one possible depth-first search tree is A B C D →E→F. Based on this depth-first search tree, indicate which arcs of this graph are tree arcs, forward arcs, backward arcs, and cross arcs. E D B Assume this directed graph is represented using adjacency lists, but do not assume any particular ordering of the arcs on the adjacency lists. (a) Find all possible depth-first search trees starting at node E. If not all nodes are included in a single tree, determine the remaining trees in the forest starting at unvisited nodes in alphabetical order. For each depth-first search tree/forest, label nodes with their postorder numbers. (b) If the adjacency lists are ordered alphabetically based on the node names (i.e., A comes first and F last), which of the depth- first search trees from part (a) will be generated? (c) Starting at node A, one possible depth-first search tree is A B C D →E→F. Based on this depth-first search tree, indicate which arcs of this graph are tree arcs, forward arcs, backward arcs, and cross arcs. E D B