The weight of minimum spanning tree in graph G, calculated using Kruskal's algorithm is :
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 15
Explanation
Take edges in increasing order: 2, 3, 4 (no cycle); 5 would close a cycle with 3 and 4, so skip it; 6 joins the last vertex. Total = 2 + 3 + 4 + 6 = 15.
More Data Structures and Algorithms questions
- What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume tha…
- In a B-Tree, each node represents a disk block. Suppose one block holds 8192 bytes. Each key uses 32 bytes. In a B-tree of order M there ar…
- Give tight bounds for T(n) = 4T(√n) + lg²n, with T(n) constant for n ≤ 2.
- Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]= 29, d[u]= 15, w…
- When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?
- The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is :