Consider the following weighted graph. Use Prim\'s algorithm starting with verte
ID: 3143035 • Letter: C
Question
Consider the following weighted graph. Use Prim's algorithm starting with vertex a to find a minimum spanning tree for the graph, and indicate the order in which edges are added to form the tree. 1) Order of adding the edges: {a, e}, {b, e}, {c, d}, {b, c}, {d, f}, {f, g} 2) Order of adding the edges: {a, e}, {b, c}, {c, d}, {d, f}, {f, g}, {b, e} 3) Order of adding the edges: {a, e}, {f, g}, {b, c}, {c, d}, {d, f}, {b, e} 4) Order of adding the edges: {a, e}, {b, e}, {b, c}, {c, d}, {d, f}, {f, g}Explanation / Answer
Since all four options start with {a,e}, we proceed from {a,e}
We find the minimum weight edge attached to a or e. Obviously {b,e} is the minimum weight edge (5).
Now, we have a,b and e. Of these, b has a minimum weight edge with c (3). So we add {b,c}.
We have a,b,c and e. The next minimum weight edge (1) is {c,d}.
The vertex d has the next minimum weight edge (2) with f. So we add {d,f}.
Finally f has the minimum weight edge (5) with the last remaining vertex g.
Thus the order of adding edges is {a,e}, {b,e}, {b,c}, {c,d}, {d,f}, {f,g} which is given in option 4.