Consider the graph shown below :
Use Kruskal's algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. 16
Explanation
Take the three weight-1 edges, then the weight-2 edges that join new components (three of them), then a weight-3 edge to the lower-left vertex and a weight-4 spoke to the bottom vertex: 3 × 1 + 3 × 2 + 3 + 4 = 16 for the 8 edges on 9 vertices.
More Data Structures and Algorithms questions
- The solution of recurrence relation : T(n) = 2T(sqrt(n)) + lg(n) is
- The elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array…
- Consider two sequences X = ⟨0, 1, 2, 1, 3, 0, 1⟩ and Y = ⟨1, 3, 2, 0, 1, 0⟩. The length of the longest common subsequence of X and Y is
- Consider the postfix expression with single-digit operands: 6 2 3 * / 4 2 * + 6 8 * −. The top two elements of the stack after the second *…
- A binary search tree is constructed by inserting the following numbers in order : 60,25,72,15,30,68,101,13,18,47,70,34 The number of nodes…
- In a ternary tree, the number of internal nodes of degree 1,2 , and 3 is 4,3 , and 3 respectively. The number of leaf nodes in the ternary…