GATE CSE 1992 | Question: 01,ix

Question

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______

Comments

Answer should be: $O(E)$

Answer 1

IF EDGES ARE ALREADY SORTED, THEN IN WORST CASE WE HAVE TO TRAVERSE THE WHOLE EDGES TO GET MINIMUM SPANNING TREE. M EDGES WILL BE TRAVERSED AND WE HAVE TO DO UNION OPERATION WHICH TAKE O(LOGN) TIME, SO COMPLEXITY WILL BE Mlog(n).

Answer 2

Since the edges are sorted, we simply need to visit the vertex, and select an edge.

Now, Selecting an edge means, check if the edge creates a cycle or not and if not then insert. It does not consume a lot of time, we can assume it to be an O(1) operation.

So we need to visit all the vertices: O(n)

And we need to perform Select operation for m edges: O(m) (worst case).

So overall time complexity is O(m+n).

Answer 3

O(n log n)

 

Answer 4

The Time complexity of Kruskal’s Algorithm is:

$O(E \cdot logE + E \cdot \alpha)$

Where the term:

$E \cdot logE$ $=>$ Time required for sorting the edges

$E \cdot \alpha$ $=>$ Time required to find the cycle (which is equal to $\alpha$) for each Edge $E$.

Interestingly there are two ways to find a cycle in a graph, which takes time as:

1. DFS: where $\alpha = O(V+E)$
2. Union-Find Structure: where $\alpha = O(1)$

Generally, since Union-Find Structure (its not there in GATE syllabus till now) outperforms DFS in this case, we use the same for detecting cycle in minimum time.

Therefore, our total time complexity becomes: $O(E \cdot logE + E)$

Now, it was given in the question that edges are already sorted.

Hence Time complexity will be: $O(E)$