The Gateway to Computer Science Excellence
+2 votes
510 views

Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges in which they are added to construct Minimum Spanning Tree (MST)?

image:n104.PNG

  1. P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T
  2.   P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T
  3.   P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T
  4.   P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
in Algorithms by Active (3.1k points) | 510 views
0
option-3 ?

3 Answers

+6 votes
Best answer

option B

by Boss (15k points)
edited by
0
Check option b after P-Q it is P-X in option not Q-X
0 votes

Assuming you have knowledge of How prim algo works I have explained this answer.

(2)

by Active (1.2k points)
0 votes

The main thing is in prims algorithm is that when you at a node then you have to choose least weight edge unless it is not forming the cycle. Follow this rule you will get the correct answer as option B.

by (117 points)
0
You are saying about kruskal.  ???

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
50,737 questions
57,292 answers
198,221 comments
104,908 users