The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
9 views
The least running time of creating spanning tree from connected graph  in G(E, V) is 
  1. O (V log V) 
  2. O (E + V log V)
  3. O (E log V)    
  4. O (V log V + E log V)
    Where E, V are respectively number of edges & vertices in the graph. 
in Others by Boss (16.1k points) | 9 views

1 Answer

0 votes
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.
ago by Active (3.8k points)
edited ago by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,984 questions
55,135 answers
190,487 comments
85,105 users