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$
  • $\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 '18 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 '18 at 19:02
  • $\begingroup$ @Thinker, in your comment above, instead of Ackerman function, f(N) should be the inverse Ackerman function of N. $\endgroup$ – Apass.Jack Aug 6 '18 at 19:37
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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