Log In
1 vote

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 value, if we choose min as 'd' 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.

in Algorithms 471 views
Min spanning tree is all about edges I think so why you are considering vertex? From my point of view in this graph we have two spanning tree of equal weight as you mentioned. :
1st one : edges :{(a,b),(b,c),(c,i),(i,d)} total weight : 21

2nd one : edges :{(a,b),(a,d),(d,i),(i,c)} total weight : 21
Thnx for the answer. My dobuts cleared. I've done calculation mistake.

And for the part "prism consider edges" yes it is true, but while executing algorithm for it (i mean real Algorithms not pseudo shortcut we use to calculated MST just by seeing it), there are key[v] (key value) and π[v](parent of v) for each vertex v in graph according to which edges are processed and MST is obtained.
You will get correct answer in either of the cases. If you take d, then next vertex will be i and then c.

Please log in or register to answer this question.

Related questions

2 votes
3 answers
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)? P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
asked Nov 17, 2017 in Algorithms Parshu gate 959 views
3 votes
2 answers
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
2 answers
Hello, I have doubt regarding prims algorithm 1)should we choose the lowest cost edge and then implement algo further? 2)Or we choose any vertex and then lowest cost edge of that vertex?
asked Nov 24, 2017 in DS JPranavc 150 views
1 vote
0 answers
suppose that a graph G has MST already computed. How quickly can we update the MST if we add a new vertex and incident edges to it. I know for the best case scenario when a single edge is incident from the newly added vertex. but for the worst case, when ... many edges. This will end up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.
asked Aug 19, 2018 in Algorithms aambazinga 430 views