Find a minimum spanning tree for a weighted graph using Prim's or Kruskal's algorithm

Prim's algorithm steps:

Step 1: Start with $A$. Add the cheapest edge from $A$ to any other vertex, say $A$-$C$ with weight $3$.

Step 2: From the current tree $\{A, C\}$, find the cheapest edge connecting to a vertex not yet in the tree. Say $C$-$D$ with weight $4$.

Step 3: Continue. From $\{A, C, D\}$, the cheapest external edge might be $D$-$B$ with weight $5$.

Step 4: From $\{A, B, C, D\}$, the cheapest external edge might be $B$-$E$ with weight $6$.

Step 5: From $\{A, B, C, D, E\}$, the cheapest external edge might be $E$-$F$ with weight $7$.

Final MST: edges $AC, CD, DB, BE, EF$, total weight $3 + 4 + 5 + 6 + 7 = 25$.

Markers reward a clear step-by-step working, the edges in order added, no edges that form cycles, and the final total weight. The exact edges depend on the network in the question.

Sort all edges by weight (Kruskal's algorithm). Add them in order from smallest to largest, but skip any edge that would create a cycle.

For $5$ towns, the MST has $5 - 1 = 4$ edges.

Worked example with hypothetical weights: edges sorted $AB(8), CD(10), AC(12), BD(15), DE(18), \ldots$.

Add $AB(8)$: tree $\{AB\}$.

Add $CD(10)$: tree $\{AB, CD\}$. Disconnected, but no cycle yet.

Add $AC(12)$: tree $\{AB, CD, AC\}$. Now connects the two components.

Skip $BD(15)$ if it would create a cycle in $\{ABCD\}$. (It does: $A$-$B$-$D$ and $A$-$C$-$D$ both exist.) Skip.

Add $DE(18)$: tree $\{AB, AC, CD, DE\}$. All $5$ vertices connected.

Total: $8 + 10 + 12 + 18 = 48$ km.

Markers reward sorting, the cycle-check at each step, and the total weight with units.

List the edges. There are three possible cables: $AB = 5$, $BC = 8$, $AC = 12$. With $3$ towns the spanning tree needs $3 - 1 = 2$ edges.

Add the cheapest edges that do not form a cycle (Kruskal's). Sorted by length: $AB(5)$, $BC(8)$, $AC(12)$.

• Add $AB$ ($5$): the tree is $\{AB\}$.
• Add $BC$ ($8$): this brings in $C$, so all three towns are joined.
• The edge $AC$ ($12$) would now close the triangle $A$-$B$-$C$, making a cycle, so it is skipped.

State the result. The minimum spanning tree uses $AB$ and $BC$.

Check. Two edges join all $3$ towns with no cycle, and $13$ km is cheaper than any tree using the $12$ km route. The MST length is $13$ km.

Sort the edges by weight. The four edges in increasing order are $RS(3)$, $PQ(4)$, $QR(6)$, $PS(9)$. A tree on $4$ vertices has $4 - 1 = 3$ edges.

Add edges in order, skipping any that make a cycle (Kruskal's).

• Add $RS$ ($3$): tree $\{RS\}$.
• Add $PQ$ ($4$): tree $\{RS, PQ\}$, two separate pieces but no cycle.
• Add $QR$ ($6$): this links the two pieces, so all four vertices are connected.
• Stop: $3$ edges are in, so $PS$ ($9$) is not needed (it would form a cycle).

Total weight.

Check. Three edges connect all $4$ vertices with no cycle. Leaving out the most expensive edge $PS$ ($9$) is what makes the tree minimal, so the MST weight is $13$.

Count the edges needed. With $4$ vertices the spanning tree has $4 - 1 = 3$ edges. Sort the five edges: $CD(4)$, $AC(5)$, $AB(6)$, $AD(7)$, $BC(9)$.

Apply Kruskal's algorithm.

• Add $CD$ ($4$): tree $\{CD\}$.
• Add $AC$ ($5$): brings in $A$, joining it to $C$ and $D$.
• Add $AB$ ($6$): brings in $B$, so all four vertices are connected.
• The next edge $AD$ ($7$) would close a cycle $A$-$C$-$D$, so skip it; $BC$ ($9$) is also not needed.

Total weight.

Check. Three edges, all vertices joined, no cycle. The two unused edges ($7$ and $9$) are both heavier than every chosen edge, confirming the tree is minimal. The MST weight is $15$.

Set up. Every pair of tanks can be joined, so there are $6$ possible pipes. A spanning tree on $4$ tanks needs $4 - 1 = 3$ pipes. Sort by length: $AC(5)$, $CD(6)$, $AB(7)$, $BD(8)$, $BC(9)$, $AD(12)$.

Apply Kruskal's algorithm.

• Add $AC$ ($5$): tree $\{AC\}$.
• Add $CD$ ($6$): brings in $D$.
• Add $AB$ ($7$): brings in $B$, so all four tanks are joined.
• Stop: $3$ pipes are in. The edges $BD$ ($8$), $BC$ ($9$) and $AD$ ($12$) would each close a cycle, so they are skipped.

Least total length.

Check. Three pipes connect all four tanks with no loop, and the three cheapest usable pipes were taken. The minimum length of pipe is $18$ m.

Start the tree at $A$ (Prim's)

The tree begins as $\{A\}$. At each stage take the cheapest edge from a tree vertex to a vertex not yet included.

Stage 1

Edges leaving $A$ are $AB$ ($3$) and $AE$ ($9$). Cheapest is $AB$ ($3$); $B$ joins. Tree $\{A, B\}$.

Stage 2

Crossing edges from $\{A, B\}$ are $AE$ ($9$), $BC$ ($7$), $BD$ ($6$). Cheapest is $BD$ ($6$); $D$ joins. Tree $\{A, B, D\}$.

Stage 3

Crossing edges are $AE$ ($9$), $BC$ ($7$), $CD$ ($5$), $DE$ ($4$). Cheapest is $DE$ ($4$); $E$ joins. Tree $\{A, B, D, E\}$.

Stage 4

Only $C$ remains. Crossing edges are $BC$ ($7$) and $CD$ ($5$). Cheaper is $CD$ ($5$); $C$ joins. All five vertices are now connected.

Result

Edges added in order: $AB$, $BD$, $DE$, $CD$.

Check. Four edges join all $5$ vertices with no cycle. The expensive edge $AE$ ($9$) was never the cheapest crossing edge, so it is left out, confirming the MST weight is $18$.

Begin at $A$ (Prim's)

Tree $\{A\}$. Each stage adds the cheapest cable from a connected town to an unconnected town.

Stage 1

From $A$: $AB$ ($8$), $AC$ ($5$). Cheapest is $AC$ ($5$); $C$ joins. Tree $\{A, C\}$.

Stage 2

Crossing cables: $AB$ ($8$), $BC$ ($10$), $CD$ ($7$), $CE$ ($6$). Cheapest is $CE$ ($6$); $E$ joins. Tree $\{A, C, E\}$.

Stage 3

Crossing cables: $AB$ ($8$), $BC$ ($10$), $CD$ ($7$), $DE$ ($4$). Cheapest is $DE$ ($4$); $D$ joins. Tree $\{A, C, D, E\}$.

Stage 4

Only $B$ remains. Crossing cables: $AB$ ($8$), $BC$ ($10$), $BD$ ($9$). Cheapest is $AB$ ($8$); $B$ joins.

Result

Cables laid: $AC$, $CE$, $DE$, $AB$.

Check. Four cables connect all $5$ towns with no loop. The most expensive route $BC$ ($10$) is never used. The least total length of cable is $23$ km.

Sort all pipes by length. $BC(2)$, $DE(3)$, $AB(4)$, $BD(5)$, $AC(6)$, $EF(6)$, $CE(7)$, $CD(8)$, $DF(9)$. A tree on $6$ stations needs $6 - 1 = 5$ pipes.

Apply Kruskal's, checking each edge for a cycle.

• Add $BC$ ($2$): tree $\{BC\}$.
• Add $DE$ ($3$): tree $\{BC, DE\}$.
• Add $AB$ ($4$): brings in $A$.
• Add $BD$ ($5$): links the $\{A, B, C\}$ piece to the $\{D, E\}$ piece.
• Skip $AC$ ($6$): both $A$ and $C$ are already connected, so this makes a cycle.
• Add $EF$ ($6$): brings in $F$, the last station. Five pipes are now placed.
• Remaining $CE$ ($7$), $CD$ ($8$), $DF$ ($9$) would all make cycles, so skip them.

Total length.

Check. Five pipes connect all $6$ stations with no cycle. Where two edges tied at $6$, $AC$ made a cycle and $EF$ did not, so $EF$ was the correct choice. The MST length is $20$.

Sort the edges. $DE(5)$, $AB(6)$, $CD(7)$, $BC(8)$, $AC(9)$, $BD(9)$, $CE(10)$, $AD(11)$. A tree on $5$ vertices needs $5 - 1 = 4$ edges.

Apply Kruskal's algorithm.

• Add $DE$ ($5$): tree $\{DE\}$.
• Add $AB$ ($6$): tree $\{DE, AB\}$, two separate pieces.
• Add $CD$ ($7$): brings $C$ in with $D$ and $E$.
• Add $BC$ ($8$): links the $\{A, B\}$ piece to the $\{C, D, E\}$ piece, so all five vertices are joined.
• Stop: $4$ edges are in. The edges $AC$ ($9$), $BD$ ($9$), $CE$ ($10$) and $AD$ ($11$) would each form a cycle, so they are skipped.

Total weight.

Check. Four edges connect all $5$ vertices with no cycle, and the algorithm stopped before reaching the tied $9$ edges, so neither was needed. The MST weight is $26$.

(a) Sort the routes (Kruskal's). $EF(4)$, $DE(5)$, $CD(6)$, $AC(7)$, $CE(8)$, $BC(9)$, $FG(9)$, $BD(10)$, $DF(11)$, $AB(12)$, $EG(13)$. A tree on $7$ towns needs $7 - 1 = 6$ cables.

Add the cheapest route each time, skipping any that closes a cycle:

• Add $EF$ ($4$); add $DE$ ($5$); add $CD$ ($6$); add $AC$ ($7$).
• Skip $CE$ ($8$): $C$ and $E$ are already joined, so it makes a cycle.
• Add $BC$ ($9$): brings in $B$.
• Add $FG$ ($9$): brings in $G$, the last town. Six cables are now placed.

Edges added in order: $EF$, $DE$, $CD$, $AC$, $BC$, $FG$.

(b) Least total length.

(c) Why it is the minimum. The two edges of weight $9$, $BC$ and $FG$, connect different new towns ($B$ and $G$), so both are needed and neither makes a cycle. There is no tie-break to resolve here, and the heavier routes $BD$ ($10$), $DF$ ($11$), $AB$ ($12$) and $EG$ ($13$) all close cycles, so the total cannot be reduced.

Check. Six cables join all $7$ towns with no loop. The least total length of cable is $40$ km.

(a) Sort and apply Kruskal's. $EF(3)$, $BC(4)$, $DE(5)$, $AB(6)$, $GH(6)$, $CD(7)$, $BD(8)$, $FG(8)$, $AC(9)$, $DF(10)$, $FH(11)$, $CE(12)$, $EG(14)$. A tree on $8$ substations needs $8 - 1 = 7$ lines.

• Add $EF$ ($3$); add $BC$ ($4$); add $DE$ ($5$).
• Add $AB$ ($6$): brings in $A$. Add $GH$ ($6$): starts a separate $\{G, H\}$ piece.
• Add $CD$ ($7$): links the $\{A, B, C\}$ piece to the $\{D, E, F\}$ piece.
• Skip $BD$ ($8$): $B$ and $D$ are now in the same piece, so it makes a cycle.
• Add $FG$ ($8$): links in the $\{G, H\}$ piece, so all eight substations are joined. Seven lines placed; the rest close cycles and are skipped.

Edges used: $EF$, $BC$, $DE$, $AB$, $GH$, $CD$, $FG$.

(b) Total length.

(c) Effect of the ties. For the pair $AB$ and $GH$ (both $6$), each joins a different part of the network, so both are needed. For the pair $BD$ and $FG$ (both $8$), $BD$ closes a cycle while $FG$ does not, so $FG$ must be chosen. In every case the total is fixed: the MST total weight is always unique, only the exact edges can differ when a tie genuinely offers two cycle-free choices.

Check. Seven lines connect all $8$ substations with no cycle. The total length is $39$.

(a) Apply Kruskal's algorithm. Sort the routes: $CF(2)$, $DE(6)$, $AB(7)$, $AC(9)$, $EF(9)$, $BC(10)$, $CD(11)$, $AF(14)$, $BD(15)$. A tree on $6$ sites needs $6 - 1 = 5$ cables.

• Add $CF$ ($2$); add $DE$ ($6$); add $AB$ ($7$).
• Add $AC$ ($9$): links the $\{A, B\}$ piece to the $\{C, F\}$ piece.
• Add $EF$ ($9$): links the $\{D, E\}$ piece in, so all six sites are connected. Five cables placed.
• Skip $BC$ ($10$), $CD$ ($11$), $AF$ ($14$), $BD$ ($15$): each would close a cycle.

Minimum spanning tree: $CF$, $DE$, $AB$, $AC$, $EF$.

(b) Test the proposed tree. The proposed routes are $AB$, $BC$, $CF$, $DE$, $EF$. Trace the connections: $A$-$B$-$C$-$F$-$E$-$D$ links all six sites in a single chain, using $5$ edges with no repeated site, so it is a valid spanning tree (connected, $6 - 1 = 5$ edges, no cycle).

Compare. The proposed tree uses $BC$ ($10$) where the MST uses the cheaper $AC$ ($9$), so it is $1$ km longer.

Check. Both networks connect all $6$ sites with $5$ cables. The MST total is $33$ km, which is $1$ km less than the proposed $34$ km, so the minimum spanning tree saves $1$ km.