CSE310 HW04 Monday 11 25 2013 Due Monday 12 02 2013 Please note that you have to typeset your assignment using either LATEX or Microsoft Word Hand written assignment will not be graded You need to submit a hardcopy before the lecture on the due date You also need to submit an electronic version via the white board For the electronic version you should name your file using the format CSE310 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 to each tree in the spanning forest it maintains Suppose we run Kruskal s algorithm on the graph G V E of the figure below with edge weights w u v as indicated Suppose that we use 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 its end vertices For example the edge connecting nodes 5 and 3 is denoted as 3 5 not 5 3 1 11 2 14 3 16 13 12 19 20 17 4 15 5 6 18 Figure 1 Graph for P1 2 pts Show the resulting disjoint set data structure in array notation after we perform all Make set i operations You should write your answer using the following format i 1 2 3 4 5 A i 6 18 pts Show the resulting disjoint set data structure in array notation at the end of each iteration 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 1 After After After After After After After After After Iteration Iteration Iteration Iteration Iteration Iteration Iteration Iteration Iteration 1 2 3 4 5 6 7 8 9 i 1 2 3 4 5 6 A i A i A i A i A i A i A i A i A i 5 pts For the graph in Fig 1 perform breadth first search from vertex 1 You should assume that the edge adjacency lists are in alphabetical order Draw the BFS tree with the vertices at the following relative positions 1 2 3 4 5 6 5 pts For the graph in Fig 1 perform depth first search from vertex 1 You should assume that the edge adjacency lists are in alphabetical order Draw the DFS tree with the vertices at the following relative positions 1 2 3 4 5 6 20 pts Figure 2 shows a directed graph G Assume that the adjacency list lists the edges in alphabetical order 2 a b c d e f Figure 2 Graph for P4 12 pts Apply depth first search DFS to graph G and show the discovery and finish times of each vertex In the main loop of DFS check the vertices in alphabetical order You can write the results on the graph in Figure 2 2 pts Draw the transpose graph GT of the graph in Figure 2 The vertices are given for your convenience a b c d e f 6 pts Apply DFS to GT to compute the strongly connected components You need to show the strongly connected components and indicate the order they are computed 3
View Full Document
Unlocking...