D1 2.1 - Minimum spanning trees
Connect every vertex of a network with the least possible total edge weight, using Kruskal's and Prim's algorithms. You will apply Prim's method directly to a matrix, handle equal weights, and check that a proposed connector really is a spanning tree.
Kruskal's algorithm
If every site must be connected, should you simply take the shortest edges? You also need to avoid paying for a cycle while leaving a site unconnected.
Recall that a spanning tree includes every vertex, is connected and contains no cycles. On vertices it has edges. The minimum spanning tree (MST), or minimum connector, minimises the sum of these edge weights. It is a set of connections, not a route which must return to its start.
Kruskal's algorithm
List edges in increasing weight order. Consider them in that order, accepting an edge unless it creates a cycle with edges already accepted. Reject such cycle-forming edges. Stop when edges have been accepted and all vertices are connected.
The accepted edges can initially form separate groups. A new edge is useful when it joins two different groups; an edge whose endpoints already have a connecting path would close a cycle. Choosing the cheapest available connection between groups avoids replacing it later by a more expensive one. This is the reason the greedy choice produces a minimum connector.
[DIAGRAM: asset_name: A network and its minimum connector; asset_slug: minimum-connector; caption: Four accepted edges connect all five vertices; BD is rejected because it closes a cycle.; description: The left panel has weighted edges AB 6, AC 7, BC 2, BD 3, CD 1, CE 8, DE 4. The right panel highlights AB BC CD DE with total weight 13. Edge BD is shown dashed as the cycle-forming rejection after CD and BC.]
Worked example 1: rejecting a short cycle edge
Use Kruskal's algorithm on vertices with edges .
Plan. Sort all edges, then test connectivity of the endpoints before each acceptance.
| Edge in weight order | Decision | Reason |
|---|---|---|
| Accept | Joins two vertices | |
| Accept | Joins to the group | |
| Reject | would be a cycle | |
| Accept | Joins to the group | |
| Accept | Joins the remaining vertex |
The remaining edges need not be considered after four acceptances.
Answer. MST edges , with total weight .
Check. They form the chain : five vertices, four edges, connected, no cycle. Replacing either chosen edge or by the rejected would increase the total.
Change only 's weight from to . It moves later in the ordered list, changing how is connected.
Worked example 2: a reweighted connection
Apply Kruskal's algorithm to the same network with .
Plan. Use the revised increasing order, retaining the same cycle test.
Accept ; reject because and are already connected through . Accept , then , which brings in . Stop at four accepted edges.
Answer. MST edges , total .
Check. Vertex has only two incident edges, now of weights and . The selected connector uses the cheaper one, and all five vertices connect through or .
Rejection is part of the trace, even when the rejected edge has a small weight.
Watch out
Taking the four smallest weights would include the cycle and leave out. Count accepted edges, not edges considered.
Show which edges are chosen in this smaller network.
Prim's algorithm on a network
Prim's algorithm grows one connected tree from a starting vertex, so its eligible edges differ from Kruskal's.
Prim's algorithm
Start at the specified vertex, or choose one if none is specified. Select the least-weight edge joining a vertex already in the tree to one outside it. Add that edge and its new vertex. Repeat until every vertex is included.
At each step consider edges from any included vertex, not just the last vertex added. Ignore edges between two included vertices and edges between two outside vertices. Every chosen edge adds a new vertex, so no cycle is formed. Selecting the cheapest edge across the included/outside boundary is the safe greedy choice.
Worked example 3: growing from A
Apply Prim's algorithm starting at to the original five-vertex network: .
Plan. Record the included set and select the cheapest edge crossing its boundary.
| Included before selection | Edge selected | New vertex |
|---|---|---|
At the third selection, is cheaper than , even though is also eligible.
Answer. Edges in order: ; minimum total .
Check. The resulting edge set agrees with Kruskal's, though the order differs. Each selection introduced exactly one of the four vertices outside the start.
Change only the starting vertex from to . A different trace can give the same MST.
Worked example 4: growing from E
Apply Prim's algorithm to the same network starting at .
Plan. Rebuild the included set from , always considering the whole boundary.
For the final step, the cheapest connection to is , even though is not adjacent to the starting vertex .
Answer. , total .
Check. Reversing the names of undirected edges gives the same four edges as before. Changing the start has not changed the minimum possible weight.
The method is about a growing set of vertices, not a traveller moving from place to place.
Watch out
Do not choose the shortest edge from only the most recently added vertex. Reconsider all included vertices at every step, and do not add a return edge after all vertices are included.
Use a new network to record the growth explicitly.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account