Question: Assume this directed graph is represented using adjacency lists, but do not assume any particular ordering of the arcs on the adjacency lists. (a)
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 EF. 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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
