Sort every edge by weight and walk the list once. Take an edge when its two ends lie in different pieces of the forest built so far; reject it when they lie in the same piece, because it would close a cycle. The whole algorithm is the sort plus a structure that answers same piece or not, and the cut property is what says each taken edge is safe.
Core ideas
The hard idea is which cut justifies each taken edge, because the algorithm never names one. The other two are the rejection rule and what the counts measure.
When the algorithm takes an edge joining two different pieces, let S be the piece containing one of its ends. Every crossing edge of that cut is still unexamined or already rejected, and every unexamined edge is at least as heavy, because the list is sorted. So the edge being taken is a lightest crossing edge of that cut, and the cut property applies. The algorithm never computes S; the argument does.
An edge whose ends are already in the same piece closes a cycle with edges the algorithm has already taken, and every one of those is at most as heavy because they came earlier in the sorted list. So the rejected edge is a heaviest edge on that cycle. Discarding it for ever is therefore justified rather than merely convenient. On the lab's opening graph three of the nine edges are rejected, each for that reason, and the panel prints the reason per edge.
The sort is Θ(E log E), which is Θ(E log V) because E < V². What remains is two find operations per edge and one union per taken edge. On the opening graph the panel counts 18 finds, 6 unions and 10 pointer hops on nine edges and seven vertices — and the hop count is the part that depends on the structure rather than on the graph, which is what makes it worth measuring separately.
The material
The algorithm, why each taken edge is safe, why each rejected edge is dead, and what the three counters mean.
The operations on pieces are exactly the two a disjoint-set structure provides, and Data Structures' “Union–Find” costs them. This lesson uses the operations and re-derives none of their analysis; what it does measure is how many of each this algorithm performs, which is a property of the algorithm rather than of the structure.
On a connected weighted graph, the set of edges the algorithm takes is a spanning tree of least total weight.
It is a forest at every step, because an edge is taken only when its ends are in different pieces, which is exactly the condition for it not to close a cycle. It ends spanning: if two pieces remained, connectivity gives an edge between them, and that edge would have been taken when the list reached it.
It is minimum by induction on the number of edges taken, with the invariant that the current forest is contained in some minimum spanning tree. Empty at the start, so the invariant holds. Suppose it holds before an edge e is taken, with the forest inside a minimum tree T. Let S be the piece containing one end of e. No edge of the forest crosses that cut, and every crossing edge is either unexamined — hence at least as heavy as e — or was rejected, which cannot happen to a crossing edge while S is a piece. So e is a lightest crossing edge, and by the exchange in the cut property there is a minimum tree containing the forest and e. The invariant survives, and at the end the forest is a spanning tree inside a minimum tree, so it is one.
□
The lab opens on 1-2 4, 1-3 3, 2-3 2, 2-4 5, 3-4 7, 4-5 1, 5-6 6, 5-7 8, 6-7 2. Sorted, the list is 4-5 at 1, 2-3 at 2, 6-7 at 2, 1-3 at 3, 1-2 at 4, 2-4 at 5, 5-6 at 6, 3-4 at 7, 5-7 at 8. The algorithm takes the first four, rejects 1-2, takes 2-4 and 5-6, then rejects 3-4 and 5-7. Total weight 19, on six edges for seven vertices. The counters read 18 finds, 6 unions and 10 pointer hops. An independently written Kruskal, from another Subject and with its own representation, is handed the same graph and returns 19.
Read the rejections. 1-2 at weight 4 is refused because 1 and 2 are already joined through 3, by the edges 2-3 at 2 and 1-3 at 3, and 4 is heavier than both — it is the heaviest edge on that triangle. 3-4 and 5-7 are refused for the same reason on their own cycles. No rejected edge is ever reconsidered, and the cycle property is why that is sound rather than greedy.
Finds are two per edge examined, so 18 on nine edges, whatever the graph looks like. Unions are one per taken edge, so V - 1 on a connected graph, so 6 here. Neither of those is interesting on its own. The hops are: they count how far each find had to walk up the parent pointers, and that depends on how the unions happened to be arranged.
The lab's chain preset makes this visible. On 1-2 1, 2-3 2, 3-4 3, 4-5 4, 5-6 5, 1-6 9 the unions build a line, and the counters read 12 finds, 5 unions and 5 hops for weight 15. The complete graph on five vertices goes the other way: ten edges, four taken and six rejected, 20 finds, 4 unions and 18 hops for weight 7. The hop count is the only one of the three that moved for a reason other than the number of edges.
This implementation deliberately does neither union by rank nor path compression, so the hop count is a real measurement of an unassisted structure. With those two refinements the finds and unions would be identical and the hops would collapse, which is precisely the point: the refinements change the cost of the structure and not the behaviour of the algorithm.
On 1-2 1, 2-3 2, 4-5 3, 5-6 4 the list runs out after four edges are taken, one short of the five a spanning tree of six vertices needs. The panel reports that it does not span, rather than presenting a forest of weight 10 as though it were a tree. The result is still the minimum spanning forest, and it is still the right answer to a slightly different question — but the difference is exactly the kind a caller has to be told about.
Measurement beside bound, last time. On the opening graph: 18 finds, 6 unions, 10 hops, and a sort of nine items. Those are counts for that graph. The bound is O(E log V) on every graph and it is dominated by the sort: the finds are 2E exactly, the unions are at most V - 1 exactly, and the hops are what the disjoint-set analysis bounds. The measured hop count on the complete graph — 18, on twenty finds — is evidence about an unassisted structure on one input, and nothing more.
Interactive
Every rejection is the cycle property, and the cost is the sort plus two finds an edge
Method
Sort once, then ask one question of each edge in turn.
Ties may be broken any way; the lemma covers it, and two different tie-breaks give two different minimum trees of the same weight. What must not happen is re-sorting or revisiting: the proof depends on every unexamined edge being at least as heavy as the current one.
The test is whether the two ends have the same representative, which is a question about the forest built so far and not about the edge. A reader tracking connected pieces by eye will get this right on six vertices and wrong on twenty; the structure exists because the question is asked 2E times.
A rejected edge closes a cycle with edges already taken, all of them at most as heavy, so it is a heaviest edge on that cycle and is in no minimum tree. Writing the reason down turns a discarded edge into an application of the cycle property, and it is what the lab's third column prints.
Anything less means the graph was not connected, and the honest report is a minimum spanning forest with the number of pieces named. Presenting a forest as a tree is the failure mode this algorithm has, because nothing in its inner loop notices.
The graph is 1-2 4, 1-3 3, 2-3 2, 2-4 5, 3-4 7, 4-5 1, 5-6 6, 5-7 8, 6-7 2. Seven vertices, so a spanning tree needs six edges.
The find column is the whole algorithm. It is not the vertex numbers; it is the representative of each end's piece, which is why 1-2 shows 3 and 3 — by then 1, 2 and 3 have all been merged and 3 is the representative. The rejection is that equality and nothing else.
The two edges of weight 2 were both taken, and they could have been examined in either order with the same result, because they touch no common vertex. Where a tie does matter, the two orders give two different trees of the same weight, and the enumeration in “The Cut Property” is what tells you how many such trees exist.
For a faded rehearsal, change the weight of 1-2 from 4 to 1 and predict the new tree before running it. The supplied first move is this: 1-2 now ties with 4-5 at the top of the list and is examined before 2-3 and 1-3, so it is taken. Say which edge is rejected in its place, and whether the total weight changes.
You should be able to sort the edges, maintain the pieces, name the cut that makes each taken edge safe, name the cycle that makes each rejected edge dead, read the three counters and say which of them depends on the structure rather than on the graph, and check the result against V - 1.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.