What is the correct vertex order of Prim algorithm from this graph?

315 views Asked by At

I want to know the vertex order of the Prim algorithm from this graph: enter image description here

My answer is {a,c,b,e,f,g,d}, but others said {a,c,b,e,d,f,g} or {a,c,d,e,b,f,g}.

Which answer is correct?

1

There are 1 answers

0
Selçuk Cihan On

Correct!

The minimum spanning tree, if we choose to begin from a is as follows:

a -> c -> b-> e -> f -> g
     |
     -> d

And the order that we add the vertices to the tree is, as you found out, {a,c,b,e,f,g,d}.