COMPSCI 170 Study Guide - Midterm Guide: Multiplication Algorithm, Directed Graph, Prims
Document Summary
Midterm 1 solutions: (4 points) for the directed graph below, nd all the strongly connected components and draw the. Label each strongly connected component with all the nodes it contains. F: (8 points) execute dfs on the same graph (reproduced here for convenience) starting at node a and breaking ties alphabetically. Mark the pre and post values of the nodes with numbering starting from 1. Draw the dfs tree/forest in the box below: 3: (4 points) in the dfs execution from above, mark the following edges as as t for tree, f for forward, B for back and c for cross. (no justi cation necessary) 4. (a) (4 points) draw a strongly connected graph with 6 vertices with the smallest possible number of edges in the box below. F (b) (2 points) in general, the minimum number of edges in a strongly connected directed graph with n vertices is n (no justi cation necessary)
