Consider the undirected graph below: Using Prim's algorithm to construct a…
2004
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
- A.
(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)
- B.
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)
- C.
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
- D.
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
Attempted by 227 students.
Show answer & explanation
Correct answer: D
Prim's algorithm run starting at node A:
Step 1 — Tree = {A}. Available edges from A: (A,D)=7, (A,B)=10, (A,C)=22. Choose (A,D)=7 (smallest).
Step 2 — Tree = {A,D}. Available crossing edges: (A,B)=10, (A,C)=22, (D,F)=22, (D,C)=26, (B,C)=30, (B,E)=49. Choose (A,B)=10.
Step 3 — Tree = {A,D,B}. Available crossing edges: (A,C)=22 and (D,F)=22 (tie) among others. Choose (D,F)=22 (ties may be broken arbitrarily).
Step 4 — Tree = {A,D,B,F}. Available crossing edges include (F,C)=4, (F,G)=5, (A,C)=22, (B,E)=49. Choose (F,C)=4 (smallest).
Step 5 — Tree = {A,D,B,F,C}. Available crossing edges include (F,G)=5, (C,E)=10, (B,E)=49. Choose (F,G)=5.
Step 6 — Tree = {A,D,B,F,C,G}. Available crossing edges include (G,E)=2 and (C,E)=10. Choose (G,E)=2 (smallest) to add E.
Final MST edges in the chosen order: (A,D), (A,B), (D,F), (F,C), (F,G), (G,E). Total weight = 7 + 10 + 22 + 4 + 5 + 2 = 50.
Why other orders fail: any valid Prim ordering must at each step pick an edge that connects a node already in the tree to a node outside it, and it must be a minimum-weight such edge. Sequences that pick an edge not incident to the current tree, or pick a heavier edge before a strictly lighter available crossing edge, are invalid.
A video solution is available for this question — log in and enroll to watch it.