+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.

| 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.