D1 2.1 - Minimum spanning trees
You will find a minimum connector using Kruskal's and Prim's algorithms, show the order of selected arcs, and move between a weighted network and its matrix.
Connecting every node as cheaply as possible
Can a correct minimum-connector algorithm choose an arc of weight before an arc of weight ? It can. The answer depends on which algorithm you use, because their rules for eligible arcs differ.
You already know
A tree is connected and has no cycles. A tree on nodes has arcs. Arc weights are supplied data; their drawn lengths do not determine their weights.
Imagine installing cables between five buildings. You need every building connected, possibly through others; you do not need a direct cable between every pair. A cycle would provide a redundant connection, so a cheapest connector can be sought among trees.
[DIAGRAM: asset_name: A network and one minimum connector; asset_slug: 9fm0-d1-166-minimum-connector; caption: The blue arcs connect all five nodes without a cycle, with total weight 17.; description: A connected five-node network with weights AB2, AC3, BC4, BD5, CD6, CE7, DE8 and BE9, with AB, AC, BD and CE highlighted as a spanning tree.]
Minimum spanning tree
A spanning tree of a connected undirected graph is a subgraph containing every node and forming a tree. A minimum spanning tree, or minimum connector, has the least total arc weight among all spanning trees of the network.
The minimum is the total weight of the chosen arcs. This is different from finding a shortest path between two specified nodes: a minimum spanning tree need not give the shortest route between every pair.
For positive connection costs, deleting an arc from a cycle preserves connectedness and reduces cost. That explains why redundant cycles are unnecessary. With equal weights there can be several minimum trees, but their minimum total is the same. The algorithms below find one.
Key idea
A minimum spanning tree connects all nodes with no cycle and minimises the sum of the chosen arc weights. It is a network of connections, not necessarily one continuous route.
Check the whole structure rather than only the number of arcs.
Kruskal's algorithm
Kruskal looks at the whole network in increasing weight order. Its selected arcs may initially form separate pieces; rejecting cycles is what keeps those pieces capable of joining into a tree.
Kruskal's algorithm
List the arcs in increasing weight order. Consider each in turn, accepting it unless it creates a cycle with the accepted arcs. Stop when arcs have been accepted for the nodes of the connected network.
Equal-weight arcs may be considered in either order unless a tie rule is specified. We use alphabetical arc order to make the displayed trace reproducible. A rejected arc stays rejected. Check whether its endpoints are already connected by accepted arcs; if so, adding it would create a cycle.
Not in the formula booklet: learn it.
Worked example 1: skipping cheaper arcs that create cycles
Question. Use Kruskal's algorithm on the network with arc weights
List the accepted arcs in order and find the minimum weight.
Plan. Scan the weights in increasing order, record rejections and stop after four accepted arcs.
| Arc | Weight | Decision | Reason |
|---|---|---|---|
| Accept | First connection | ||
| Accept | Joins to the selected part | ||
| Reject | Creates cycle | ||
| Accept | Joins | ||
| Reject | are already connected | ||
| Accept | Joins ; four arcs selected |
Why reject even though it is cheaper than ? It joins nodes already connected through , so it would create a cycle rather than connect a new component.
Answer. Accepted order: . Minimum weight:
Check. All five nodes are connected by four arcs with no cycle. The highlighted tree in the diagram has these arcs.
Worked example 2 changes only , from weight to weight . A tie now gives a genuine choice.
Worked example 2: equal weights
Question. Use Kruskal's algorithm when
Use alphabetical arc order to break ties.
Plan. Retain increasing weight order, placing before , and continue checking cycles.
| Arc | Weight | Decision | Reason |
|---|---|---|---|
| Accept | No cycle | ||
| Accept | No cycle | ||
| Reject | Completes the triangle | ||
| Accept | Adds | ||
| Reject | Its endpoints are now connected | ||
| Accept | Adds the last node |
Why state the tie choice? It explains why , rather than , enters this particular tree. If were considered first, it could be accepted and rejected instead.
Answer. This trace gives , of weight . The alternative is also a minimum tree of weight .
Check. In either tree the two tied arcs contribute exactly one weight of ; both trees connect all nodes without a cycle.
Here the repeated weights produce two minimum trees. Equal weights do not always produce several minimum trees; it depends on which alternatives can actually be exchanged.
Watch out
Wrong: take the four cheapest arcs regardless of their connections. Right: every accepted arc must avoid a cycle. Show rejected arcs where they explain why a larger weight is selected.
Introduce a second tie in the matched trace.
Prim's algorithm from a specified node
Prim grows one connected tree from its starting node. At each step it considers all arcs from the selected set to an unselected node, not just arcs from the most recently added node.
Prim's algorithm
Start at the specified node. Choose a least-weight arc joining a selected node to an unselected node, add that arc and the new node, and repeat until every node is selected.
An arc with both ends selected is ineligible, even if it is cheap. An arc with neither end selected is also ineligible for now. A tie may be resolved either way unless instructed otherwise. Prim never creates a cycle because each accepted arc adds a new node.
Not in the formula booklet: learn it.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account