717 views
1 votes
1 votes
Which one of the following is true?

1) For any graph G Kruskal and Prims both give same MST.

2)The running time of Prims algo can be improved if we use Fibonacci Heap instead of Min-Heap.

3) Kruskal Algorithm uses disjoint set of data structure.

1 Answer

Best answer
1 votes
1 votes

1. Not always correct. Multiple MST case

2. Yes. using Fibonacci heap $E + V \log V$

3. Yes. Union-Find is used. (nice application + implementation + reference)

edited by

Related questions

0 votes
0 votes
1 answer
1
Hira Thakur asked Dec 9, 2016
368 views
how many numbers of MST possible for n vertex:1. all the weight edges are distinct2. all the weight edges are different
0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
4
Naveen Kumar 3 asked Nov 10, 2018
629 views
Let us assume that $G$($V$, $E$) is a weighted complete graph such that weight of the edge <$V_K$,$V_L$>=2|$K$-$L$|. The weight MST of $G$ with 100 vertices is __________...