Time complexity of kruskal using array data structure

Question

I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps:

1. Sort the edges as per there edge weights. O(ElogE)
2. And then select edges one by an check by the union and find algorithm if they form a cycle or not. Time for this step for the single edge will be O(logv) so for E edges it will be O(ElogV).

Time complexity according to this implementation is O(ElogE)+O(ElogV)

For Desnse graph E=O(V^2) so time is O(ElogV^2) + O(Elogv) = O(Elogv)

But now the question is How to implement Kruskal using array data structure. From above algorithm step, 1 will remain the same So time for sorting edges will be O(ElogE)

But how to implement the second step using array data structure without using Disjoint-set data structure?

If I store each set of disjoint set in an array then the second step will take O(V) time for each edge. So total time will O(EV) for the second step. So total time for Kruskal using array data structure will be O(ElogE)+O(EV).

But questions in the below link does not have this option where I am wrong in above steps?

https://gateoverflow.in/92864/kruskals-mst

Answer 1

Here is the original question encountered by the OP, quoted here so that readers do not have to register to that website just to take a look at the question.

Consider a graph with V vertices and e edges,What is the worst case time complexity for kruskal's algorithm when implemented using array data structure?
a.) E+ElogV
b.)VlogV
c.)V^2
d.)Vlog^2V

The only correct answer as I see is, the original question is ill-posed. It is ill-posed because of its unconventional, ambiguous, almost meaningless use of "using array data structure".

Array is such a fundamental data structure, it usually converys little information when you say an algorithm is implemented using array data structure. Especially in the current case of Kruskal's algorithm, we usually refer to the disjoint-set data structure used in the algorithm to keep track of which vertices are in which connected components and to determine whether an edge will join two different connected components. In fact, the whole page about Kruskal's algorithm in wikipedia does not mention "array" even once. Although well versed regarding to minimal spanning tree and Kruskal's algorithm[1], I am confused by this "using array data structure".

Let us also take a look at other aspects of the original question. It has bad capitalization, bad punctuation, and inconsistent white spacing. It introduces "$e$ edges" but use $E$ in the choices. When it lists the time complexities, it should apply the big $O$ notation such as $O(E+E\log V)$. It skips the basic description of the graph as connected edge-weighted.

All in all, it is fair to say the original question is of such a low quality, you should just ignore it. Try not to learn from it.

Answer 2

the time complexity for sorting edges wt wise is ElogE and then
while adding each edge you have to check for cycle the corresponding time complexities will be like ... 1(for detecting cycle after adding 1st edge in mst ) + 2( detecting cycle after adding 2nd edge) +3..........+(v-1). = O(v^2) hence total time complexity is ..... ElogE +V^2 = Elog E + E as V^2 is almost equal to E.

hence time complexity is ELogE