1. Suppose you perform a depth first search for the graph { (0,1), (0,2), (0,5), (1,4), (2,3), (3,8), (4,9), (5,6), (5,7), (6,7) }. Let 0 be the source. Assume vertices in adjacency list are ordered smallest int to largest int. A. Show the resulting tree (drawing a picture is best, but listing the edges in the tree is also good). B. Show the non-tree edges (either clearly indicate in picture or list them). C. List the vertices in order of start time. D. List the vertices in order of finish time. 2. Suppose you run breadth first search on the same graph. A. Show the resulting tree (drawing a picture is best, but listing the edges in the tree is also good). B. Show the non-tree edges (either clearly indicate in picture or list them). C. For the non-tree edges, indicate whether they connect a node on the same level or on a different level. D. List the vertices in the order visited (start time).
1. Suppose you perform a depth first search for the graph { (0,1), (0,2), (0,5), (1,4), (2,3), (3,8), (4,9), (5,6), (5,7), (6,7) }. Let 0 be the source. Assume vertices in adjacency list are ordered smallest int to largest int.
A. Show the resulting tree (drawing a picture is best, but listing the edges in the tree is also good).
B. Show the non-tree edges (either clearly indicate in picture or list them).
C. List the vertices in order of start time.
D. List the vertices in order of finish time.
2. Suppose you run breadth first search on the same graph.
A. Show the resulting tree (drawing a picture is best, but listing the edges in the tree is also good).
B. Show the non-tree edges (either clearly indicate in picture or list them).
C. For the non-tree edges, indicate whether they connect a node on the same level or on a different level.
D. List the vertices in the order visited (start time).
Trending now
This is a popular solution!
Step by step
Solved in 6 steps with 2 images
