Question

How much work must Kruskal's MST algorithm do before it starts choosing edges for its MST? Assume the undirected graph has n vertices and m edges. Explain the necessary preliminary work and its big-O cost if done efficiently What are the best case and worst case for Kruskal's MST algorithm with parameters n and/or m? Explain your answer.

Answer 1

In Kruskal's algorithm, before selecting the edges for MST, we have to sort the edges in ascending order of weights and then we start selecting edge with minimum weighted edge among the remaining edge will be selected which does not form cycle.

Hence the preliminary work includes:-

1. Sort the edges in ascending order of weights which will take O(m log m).

2. Create a set for each vertex v in graph using MAKE_SET operation which will take O(n) time. This is done in order to check for cycle, if it can form while selecting an edge.

Hence time complexity to do preliminary work is O(n + m log m).

In Kruskal's algorithm, in best case sorting of edges can be done in O(m) time( using insertion sort) . Then in best case, every time the minimum spanning tree can grow as single connected component and hence combining the vertices will take O(n) time. So total complexity will be O(m+n).

In worst case, sorting will take O(m log m) time (using merge sort). Then combining the vertices using FIND and UNION method will take O(log n) time. Hence doing this while adding each edge will take O(m log n) time.

Hence in worst case, time complexity will be O(m log m) + O(m log n) = O(m log (mn))

Please comment for any clarification.