Exercise 2: Prim's Algorithm for Office Network Cabling — Possible Solution
====================================================================

GIVEN
------------------------------
Office1-Office2(8), Office1-Office3(5), Office2-Office3(3),
Office2-Office4(9), Office3-Office4(4)
Starting vertex: Office1

STEP 1: START THE TREE AT Office1
------------------------------
Tree so far: {Office1}
Frontier edges available: Office1-Office2(8), Office1-Office3(5)

STEP 2: REPEATEDLY ADD THE CHEAPEST FRONTIER EDGE
------------------------------
Cheapest available: Office1-Office3(5) -> ADD Office3.
Tree so far: {Office1, Office3}
New frontier edges from Office3: Office3-Office2(3),
Office3-Office4(4) - both now available alongside the still-
unused Office1-Office2(8)

Cheapest available: Office3-Office2(3) -> ADD Office2.
Tree so far: {Office1, Office3, Office2}
(Office1-Office2(8) is now useless - Office2 is already in the
tree, so this edge is simply never picked, not specially
removed)

Cheapest available: Office3-Office4(4) -> ADD Office4.
Tree so far: {Office1, Office3, Office2, Office4} - all 4 offices
connected, done.

RESULT
------------------------------
Cabling plan: Office1-Office3, Office3-Office2, Office3-Office4
Total cost: 5 + 3 + 4 = 12

Office3 ends up as the natural hub of this cabling plan, directly
connected to all three other offices, since it happened to offer
the cheapest onward connection at every step Prim's algorithm
needed one.

WHY THIS WORKS AS AN ANSWER
------------------------------
The frontier is correctly recomputed after each vertex is added
(new edges from Office3 become available only once Office3 itself
joins the tree), and the more expensive Office1-Office2(8) edge is
correctly left unused once Office2 becomes reachable more cheaply
through Office3, rather than being explicitly and separately
"rejected."