For the undirected, weighted graph given below, which of the following…

Concept

Prim's algorithm grows a Minimum Spanning Tree one vertex at a time from a chosen start: at every step, among all edges that connect a vertex already inside the growing tree to a vertex still outside it, it adds the single cheapest such "crossing" edge. An edge joining two vertices that are both already inside the tree (it would close a cycle) or both still outside it (it does not touch the tree yet) can never be picked at that step.

Reading each edge and its weight from the diagram:

• (a, b) — 1

• (a, d) — 5

• (a, c) — 6

• (b, c) — 6

• (d, f) — 2

• (d, g) — 10

• (c, f) — 3

• (c, e) — 7

• (f, h) — 8

• (g, h) — 7

• (g, i) — 3

• (i, h) — 8

• (e, h) — 12

Applying it here

Starting the tree at vertex d and, at every step, adding the cheapest edge that crosses from the current tree to a vertex not yet in it:

1. Add (d, f), weight 2 — the cheapest edge leaving the starting vertex d, compared with (d, a) = 5 and (d, g) = 10.

2. Add (f, c), weight 3 — the cheapest edge now crossing from the tree {d, f} to an outside vertex.

3. Add (d, a), weight 5 — cheaper than the other crossing edges available at this point: (d, g) = 10, (c, a) = 6, (c, b) = 6, (f, h) = 8 and (c, e) = 7.

4. Add (a, b), weight 1 — now available since a is in the tree, and the cheapest crossing edge overall at this step.

5. Add (c, e), weight 7 — the cheapest edge left crossing from {d, f, c, a, b}, compared with (f, h) = 8.

6. Add (f, h), weight 8 — cheaper than the other edge crossing to h at this point, (e, h) = 12, and cheaper than (d, g) = 10.

7. Add (g, h), weight 7 — cheaper than the alternative crossing edges (d, g) = 10 and (i, h) = 8.

8. Add (g, i), weight 3 — the last vertex i joins through the cheapest remaining crossing edge.

All nine vertices are now joined by eight edges with no cycle — a complete, valid spanning tree of total weight 2 + 3 + 5 + 1 + 7 + 8 + 7 + 3 = 36.

Cross-check

An independent method — Kruskal's algorithm, which repeatedly adds the globally cheapest remaining edge unless it closes a cycle — must build the same Minimum Spanning Tree, since the MST's total weight and edge set are unique for this graph:

1. Sort every edge by weight: 1, 2, 3, 3, 5, 6, 6, 7, 7, 8, 8, 10, 12.

2. Add (a, b) = 1 — no cycle.

3. Add (d, f) = 2 — no cycle.

4. Add (c, f) = 3 — connects c to {d, f}, no cycle.

5. Add (g, i) = 3 — starts a new component {g, i}, no cycle.

6. Add (d, a) = 5 — joins {a, b} with {d, f, c}, no cycle.

7. Skip (b, c) = 6 and (a, c) = 6 — both endpoints are already in the same growing component, so adding either would close a cycle.

8. Add (c, e) = 7 — brings in e, no cycle.

9. Add (g, h) = 7 — joins {g, i} with h, no cycle.

10. Add (f, h) = 8 — joins the two remaining components into one; all nine vertices are now connected using eight edges.

11. Skip (i, h) = 8, (d, g) = 10 and (e, h) = 12 — every remaining edge would close a cycle, so the tree is already complete.

Kruskal's method lands on exactly the same eight edges — (a, b), (d, f), (c, f), (g, i), (d, a), (c, e), (g, h), (f, h) — for the same total weight of 36, confirming the tree found above. The sequence (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i) is exactly this valid Prim execution, in the order the edges were added.