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:
- Sort the edges as per there edge weights. O(ElogE)
- 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?