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. Algorithms minimum-spanning-tree + – srestha asked Dec 9, 2016 srestha 717 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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) dd answered Dec 9, 2016 edited Dec 10, 2016 by dd dd comment Share Follow See all 4 Comments See all 4 4 Comments reply srestha commented Dec 9, 2016 reply Follow Share Why 1) not correct? example 0 votes 0 votes dd commented Dec 9, 2016 reply Follow Share Multiple MST case. Order of edge inclusion is not fixed. Although MST cost does not change 0 votes 0 votes srestha commented Dec 9, 2016 reply Follow Share Plz give link Primes using Fibonacci heap 0 votes 0 votes sudsho commented Dec 9, 2016 reply Follow Share minimum cost will be same using either kruskal or prism but tree may vary....and @sreestha i dont think fibonacci heap is in syllabus; 1 votes 1 votes Please log in or register to add a comment.