menu
search
Log In
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Prims algorithm

2 votes
946 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 946 views
0
option-3 ?

3 Answers

6 votes
 
Best answer

option B


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)

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.

0
You are saying about kruskal.  ???
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

3 votes
2 answers
1
2.2k views
Difference between Kruskal's and Prim's algorithm ?
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?
asked Jan 24, 2017 in Algorithms Kapil 2.2k views
1 vote
0 answers
2
467 views
prims algo from cormen
Here the graph that I was trying to find MST using algo in cormen.(If you need algo to ask, I supposed you have it) Algorithms uses min queue in process, my dobut is when it came to choice b/w vertex 'c' and 'd' as at that time both will ... wrong answer, so prism deal with this case? If you need algo I will given you, or just please refer chapter 23 cormen prim's algorithm.
Here the graph that I was trying to find MST using algo in cormen.(If you need algo to ask, I supposed you have it) Algorithms uses min queue in process, my dobut is when it came to choice b/w vertex 'c' and 'd' as at that time both will have 8 has key ... we get wrong answer, so prism deal with this case? If you need algo I will given you, or just please refer chapter 23 cormen prim's algorithm.
asked Aug 5, 2017 in Algorithms bhuv 467 views
1 vote
0 answers
3
349 views
Prim's algorithm for MST
Assuming that the graph can contain repeated edge weights, we have a single tree at any instance when applying Prim's algorithm. Justify this statement.
Assuming that the graph can contain repeated edge weights, we have a single tree at any instance when applying Prim's algorithm. Justify this statement.
asked Oct 30, 2017 in Algorithms just_bhavana 349 views
3 votes
1 answer
4
1.7k views
Analysis Of Prims Algorithm Time Complexity
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
asked Sep 22, 2017 in Algorithms pC 1.7k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...