Consider the following weighted graph. Use Prim’s algorithm starting with vertex
ID: 3143024 • 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.
a)Order of adding the edges: {a, e}, {b, e}, {c, d}, {b, c}, {d, f}, {f, g}
b)Order of adding the edges: {a, e}, {b, c}, {c, d}, {d, f}, {f, g}, {b, e}
c)Order of adding the edges: {a, e}, {f, g}, {b, c}, {c, d}, {d, f}, {b, e}
d) Order of adding the edges: {a, e}, {b, e}, {b, c}, {c, d}, {d, f}, {f, g}
d2 5 9 6 58 3Explanation / Answer
Ans is D) {a,e},{b,e},{b,c},{c,d},{d,f},{f,g}
Minimum Spanning Tree:- Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.
Steps of Prim's Algorithm:
The following are the main 3 steps of the Prim's Algorithm:
ALL THE BeSt DeAr ......................................... RaTE ThE AnsWer ,,,,,,,,,,,,,,,,,,,