Consider the undirected graph below: Using Prim's algorithm to construct a…

Prim's algorithm run starting at node A:

1. Step 1 — Tree = {A}. Available edges from A: (A,D)=7, (A,B)=10, (A,C)=22. Choose (A,D)=7 (smallest).

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

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

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

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

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