KPGCET-CSE-2019-33

Question

The least running time of creating spanning tree from connected graph  in G(E, V) is 

• A. O (V log V) 
• B. O (E + V log V)
• C. O (E log V)    
• D. O (V log V + E log V)
  Where E, V are respectively number of edges & vertices in the graph. 

Answer 1

Though, I feel the question contains insufficient details but still.

The prims algorithm is used when the graph is dense or the number of edges is very high as compared to the number of vertices.

Kruskal is better to be used when the graph is sparse.

Now, coming to the worst case time complexities of both the algorithms.

$PRIMS$ $:$ $O(E + VlogV)$

$KRUSKAL$: $O(ELOGV)$

Since, both of these options are given in the question, then I would chose the Kruskal since, it uses much more simpler data structures in its implementation.

$Kruskal$: Implemented by Union-Find.

$Prims$: Implemented by Fibonacci Heap.

So, answer is (C) according to me.
............................................................................................................
$Note:$ Prims can't be used for disconnected graphs unlike Kruskal.

Answer 2

For kruskal the time complexity is O (E log V)   and its least. Hence option C is the answer