398 views

2 Answers

0 votes
0 votes

In Prim's Algorithm, first a min heap is created (Build min heap) with the given nodes, such that the source node (chosen randomly) gets a key 0, and all other nodes get keys infinity.

At each interation, the node with the least key is deleted (Delete-min operation), and the keys of all the nodes adjacent to it are suitably reduced (Decrease Key).

By going with the above method, in the 4th sequence, 'd' is chosen and assigned key 0. Adjacent to 'd' are 'c', 'e', 'f'. Keys of 'c', 'e', 'f' are reduced to 2,3 and 1 respetively. In the next iteration, 'f' is chosen (f is minimum). Adjacent to it are 'c', 'e', 'b'. Keys of 'c', 'e', 'b' are made as 2,3 and 2 respectively. Now, 'c' and 'b' have the least keys.

So, the sequence should have been (d,f),(d,c)...... or (d,f),(f,b)........ Hence sequence 4 is wrong.

(Here I have followed the algorithm of Cormen)

Related questions

2 votes
2 votes
2 answers
1
techbrk3 asked Nov 16, 2017
509 views
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e)(g,f),(f,c),(g,d),(c,e),(d,b),(d,a)(c,f),(c,e),(e,d),(a,b),(d,g),(b,c)None of the above
0 votes
0 votes
0 answers
2
iita asked Jan 15, 2017
441 views
1 votes
1 votes
0 answers
3
thor asked Jan 7, 2017
554 views
What should be the insertion order of elements such that the following B+ Tree is obtained? (order of root node = 3, and leaf node = 2)
0 votes
0 votes
1 answer
4