If Kruskal’s algorithm is used for finding the minimum spanning tree of a weighted graph with n vertices and m edges and edge weights are already given in a sorted list, then, what will be the time complexity to compute the minimum cost spanning tree given that the union and find operations take amortized O(1)?
a. O(m)
b. O(n)
c. O(n logm)
d. O(m logn)
a. O(m)
As you are already given edge weights in a sorted order, you just have to pick the edges in the increasing order and add it to the current spanning set if its addition does not result in a cycle or else throw it away.
You might also like to view...
__________ is needed to represent nothing in a given position.
a. Nothing b. A space character c. The digit zero (0) d. The base
How can you move some, but not all, of the points on a path?
What will be an ideal response?
To find all individuals whose name is Francis or Frances, enter ____ in the Criteria row of the appropriate column.
A. Franc?s B. Franc*s C. Franc#s D. Franc%s
"Drag and drop" describes what operation?
A. Copying text to the Clipboard B. Moving text using the mouse C. Moving text using keyboard shortcuts D. Deleting text