Consider the undirected weighted graph below. Run Kruskal's algorithm on it and annotate the sequence of UNION operations that the algorithm performs. -12 -6 0 2 3 6 7 10 12 15 g b d c e a f For each step, write the two vertices being unioned (one vertex label per box). List the unions in the order Kruskal's performs them. If your version of the algorithm performs fewer unions than there are lines, leave the extra lines as empty (their default value). Please enter all union pairs in alphabetical order - so if two nodes x and y are being unioned, enter x,y, not y,x. That is, a < b < c < d < e < f < g. [table] Step 1: UNION(Answer 1 Question 2, Answer 2 Question 2) Step 2: UNION(Answer 3 Question 2, Answer 4 Question 2) Step 3: UNION(Answer 5 Question 2, Answer 6 Question 2) Step 4: UNION(Answer 7 Question 2, Answer 8 Question 2) Step 5: UNION(Answer 9 Question 2, Answer 10 Question 2) Step 6: UNION(Answer 11 Question 2, Answer 12 Question 2) Step 7: UNION(Answer 13 Question 2, Answer 14 Question 2) Step 8: UNION(Answer 15 Question 2, Answer 16 Question 2) Step 9: UNION(Answer 17 Question 2, Answer 18 Question 2) Step 10: UNION(Answer 19 Question 2, Answer 20 Question 2) | If you find it useful, the edge weights in the graph when sorted read [-12, -6, 0, 2, 3, 6, 7, 10, 12, 15]. All edge weights are distinct. In case you do not recall how Kruskal's algorithm works, the pseudocode from the course notes is reproduced below for reference. 1 2 3 4 5 6 7 8 9 function KRUSKAL(G = (V, E)) sort(E, key((u, v)) = w(u, v)) // ascending weight forest = UnionFind.initialise(n) T = (V, ∅) for each edge (u, v) in E do if forest.FIND(u) ≠ forest.FIND(v) then forest.UNION(u, v) T.add_edge(u, v) return T [/table]多项填空题

题目图片

登录即可查看完整答案

我们收录了全球超50000道真实原题与详细解析,现在登录,立即获得答案。

类似问题

You are running the Kruskal's algorithm to obtain the minimum spanning tree of a connected, undirected, weighted graph with 10 vertices (ID-0 to ID-9). Given the following parent array state of the union-find data structure during the algorithm's run, which of the following statement(s) is true?

Consider the undirected graph below and Kruskal's algorithm for computing a minimum spanning tree. In which order are the edges added to the solution? 1: 1st edge ____ 2: 2nd edge ____ 3: 3rd edge ____ 4: 4th edge ____ 5: 5th edge ____ 6: 6th edge ____ 7: 7th edge ____ 8: 8th edge ____

Kruskal_Algo_1 This question relates to the use of the Graph Abstract Data Type (ADT) implemented with an Adjacency Map, as covered in class. You are working with an undirected, connected, weighted graph G, where all edges have non-negative weights. The goal is to compute a Minimum Spanning Tree (MST) of G. The following pseudocode implements Kruskal’s Algorithm using a priority queue to select edges in increasing order of weight and a disjoint set forest to track connected components: KRUSKAL-MST(Graph G):    Initialize an empty list MST to store edges of the minimum spanning tree    Initialize a priority queue PQ with all edges of G, prioritized by weight    Initialize a forest where each vertex is its own component     while MST has fewer than (number of vertices - 1) edges and PQ is not empty:        Remove the edge with the smallest weight from PQ        Let (u, v) be the endpoints of the edge         if u and v are in different components:            Add edge (u, v) to MST            Merge the components of u and v     return MST Why do we remove the edge with the smallest weight at each step?

Project A has a required return on 9.2 percent and cash flows of −$87,000, $32,600, $35,900, and $43,400 for Years 0 to 3, respectively. Project B has a required return of 12.7 percent and cash flows of −$85,000, $14,700, $21,200, and $89,800 for Years 0 to 3, respectively. Which project(s) should you accept based on net present value if the projects are mutually exclusive?

更多留学生实用工具

加入我们，立即解锁 海量真题 与 独家解析，让复习快人一步！