The Gateway to Computer Science Excellence
+1 vote
284 views

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 by Active (4.8k points) | 284 views
+1
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
0
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.
0
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

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,306 answers
198,316 comments
105,012 users