0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ you miss the well-known union-find data structure, which is implemented by array. see en.wikipedia.org/wiki/Disjoint-set_data_structure $\endgroup$
    – Bangye
    Jul 3, 2018 at 10:33
  • $\begingroup$ @Bangye hi thanx for the reply i read from the wiki link provided by you and from some other links and understood that time complexity for M union and find operation will be O(N+Mf(N)) where f(N) is Ackerman function. So O(N+Mf(n))=O(V+Ef(N)) and for dense graph it is equal to O(E) so total time will be O(ElogV)+O(E) for Kruskal right? so Option A is correct. $\endgroup$
    – Thinker
    Jul 3, 2018 at 19:02
  • $\begingroup$ @Thinker, in your comment above, instead of Ackerman function, f(N) should be the inverse Ackerman function of N. $\endgroup$
    – John L.
    Aug 6, 2018 at 19:37

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 1 +2+3+4......(v-1) ........if in all cases cycle not detected and every upcoming edge is added. what if 1 edge added 2 edge added 3 rd edge cycle 4th edge cycle .....5edge added .. ... in that case also the time complexity will be V^2 aka E for cycle dtetction $\endgroup$
    – sanju
    Nov 12, 2019 at 13:38
  • $\begingroup$ Welcome to Computer Science. Please edit your answer instead of adding further information via comments. Also, this page supports LaTeX! $\endgroup$
    – ttnick
    Nov 12, 2019 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.