CSE310 HW04, Monday, 11/25/2013, Due: Monday, 12/02/2013Please note that you have to typeset your assignment using either LATEX or MicrosoftWord. Hand-written assignment will not be graded. You need to submit a hardcopybefore the lecture on the due date. You also need to submit an electronic version viathe white board. For the electronic version, you should name your file using the formatCSE310-HW04-LastName-FirstName.1. (20 pts) As we learned in class, Kruskal’s algorithm for computing a minimum spanning tree(MST) uses a disjoint-set data structure to keep information about the nodes that belong toeach tree in the spanning forest it maintains. Suppose we run Kruskal’s algorithm on thegraph G(V, E) of the figure below, with edge weights w(u, v) as indicated. Suppose that weuse union-by-rank and find-with-path-compression when performing the disjoint-set operations.Also assume that we represent each undirected edge in alphabetical order of itsend-vertices. For example, the edge connecting nodes 5 and 3 is denoted as (3, 5),not (5, 3).1 2 34 5 611121314151617181920Figure 1: Graph for P1.(2 pts) Show the resulting disjoint-set data structure (in array notation) after we perform allMake-set(i) operations. You should write your answer using the following format.i 1 2 3 4 5 6A[i](18 pts) Show the resulting disjoint-set data structure (in array notation) at the end of eachiteration of the “for each edge (u, v) in E in non-decreasing order of weights do” loop.You should write your answer using the following format.1i 1 2 3 4 5 6After Iteration 1 A[i]After Iteration 2 A[i]After Iteration 3 A[i]After Iteration 4 A[i]After Iteration 5 A[i]After Iteration 6 A[i]After Iteration 7 A[i]After Iteration 8 A[i]After Iteration 9 A[i](5 pts) For the graph in Fig. 1, perform breadth first search from vertex 1. You should assume thatthe edge adjacency lists are in alphabetical order. Draw the BFS tree, with the vertices atthe following relative positions.1 2 34 5 6(5 pts) For the graph in Fig. 1, perform depth first search from vertex 1. You should assume thatthe edge adjacency lists are in alphabetical order. Draw the DFS tree, with the vertices atthe following relative positions.1 2 34 5 6(20 pts) Figure 2 shows a directed graph G. Assume that the adjacency list lists the edges inalphabetical order.2a b cd e fFigure 2: Graph for P4.(12 pts) Apply depth first search (DFS) to graph G, and show the discovery and finish timesof each vertex. In the main-loop of DFS, check the vertices in alphabeticalorder. You can write the results on the graph in Figure 2.(2 pts) Draw the transpose graph GTof the graph in Figure 2. The vertices are given for yourconvenience.a b cd e f(6 pts) Apply DFS to GTto compute the strongly connected components. You need to showthe strongly connected components and indicate the order they are
View Full Document
Unlocking...