CS557B Algorithms Rivier University Spring 2016 HW 5 1 1. Given the directed graph: A B C D F E G Perform a depth-first search starting with vertex A, assuming an adjacency list is in alphabetical order for each vertex. List the vertices in the order they are explored. 2. Using the same graph as problem 1, perform a breadth-first, staring with vertex A, assuming an adjacency list is in alphabetical order for each vertex. List the vertices and their distance (number of edges) from vertex A in the order they are explored. 3. For each vertex in the graph for problem 1, list the in degree and out degree. CS557B Algorithms Rivier University Spring 2016 HW 5 2 4. Given the weighted graph: A B C E D F G I H 2 4 2 1 6 5 5 6 1 5 3 2 4 1 8 Execute Prims minimum spanning tree algorithm starting with vertex G. List the edges and their weights in the order they are added to the tree. Also, calculate the total weight for the spanning tree. 5. Given the weighted digraph: A B C D E F 2 2 4 7 8 4 6 4 1 3 3 2 5 Perform Dijstras shortest-path algorithm, starting with vertex F. CS557B Algorithms Rivier University Spring 2016 HW 5 3 6. Run the Edmonds-Karp flow algorithm on the flow graph below, where node s is the source and node t is the sink. a e s c t b d 0/5 0/3 0/4 0/5 0/8 0/1 0/4 0/6 0/3 0/7 0/4 0/5 0/6 (a) What is the value of the maximum flow from s to t? (b) What is the capacity of a minimum cut of this flow network? (c) List the vertices in S and T for a minimum cut. (d) For each edge that carries a non-zero flow, list the edge and the flow for that edge.