Fix the cut in advance: one side is the tree built so far, the other is everything else. The lightest edge across that boundary is safe by the cut property, so the algorithm is a loop that finds it and adds it. A heap keyed on edge weight finds it, and the interesting consequence is that entries in the heap go out of date and must be discarded when they surface.
Core ideas
The hard idea is the stale entry. The cut and the correctness are the sorted method's, restated with the choice of cut made in advance.
S starts as the single starting vertex and grows by one vertex each step. At every step the algorithm takes a lightest edge crossing the cut between S and the rest, which is exactly the hypothesis of the cut property, so every edge it takes is safe. Where the sorted method leaves the cut implicit in its proof, this algorithm maintains it explicitly, which is the only real difference between them.
Candidate edges are pushed as their tail joins S. An edge pushed while its far end was outside may have that end brought into S by a different edge before it surfaces, and then it crosses nothing. Rather than find and delete it — which a binary heap cannot do cheaply — the algorithm pops it and discards it. On the lab's opening graph that happens exactly once, to the edge between 1 and 2 at weight 4, and the panel labels the row rather than hiding it.
Starting the same graph at different vertices gives the same tree of weight 19 every time, and different amounts of work: 12 key comparisons from vertex 1, 14 from vertex 2, 24 from vertex 4 and 15 from vertex 7. That is a measurement of the heap's behaviour on one graph from four starts, and it is the clearest small example on this course of a count that moves while the answer does not.
The material
The algorithm, the correctness it inherits, what a stale entry is, and the reference column that is not a verdict.
Correctness is the cut property applied once per step, with S as the side. The edge taken is by construction a lightest edge crossing that cut, so it lies in some minimum spanning tree extending what has been built. That is the same induction the sorted method uses; only the choice of cut differs.
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, starting at vertex 1. The pops come out 1-3 at 3 adding vertex 3, 2-3 at 2 adding vertex 2, then 1-2 at 4 with both ends already in S — discarded — then 2-4 at 5 adding 4, 4-5 at 1 adding 5, 5-6 at 6 adding 6, and 6-7 at 2 adding 7. Six edges, weight 19, the same tree the sorted method built. The counters read 9 pushes, 7 pops and 12 key comparisons.
The pop order is worth a second look, because it is not sorted. 1-3 at weight 3 comes out before 2-3 at weight 2, and 2-4 at 5 before 4-5 at 1. The heap returns the lightest entry it HOLDS, and an edge is only held once its tail has joined the tree — 4-5 was not a candidate until 4 was in. That is the whole difference from the sorted method, which considers every edge in one global order.
Nine edges were pushed and seven popped. The two never popped are the two the loop stopped before reaching, and one of the seven was stale. A heap has no cheap way to find and remove an entry that is no longer wanted, so the standard answer is to leave it and test on the way out. The cost is that the heap may hold up to E entries rather than V, which is where the E log V term in the usual bound comes from.
The lab's lazy preset was built to fill the heap with such entries, and measuring it is instructive: on 1-2 1, 1-3 1, 1-4 1, 2-3 9, 2-4 9, 3-4 9, 1-5 2, 2-5 3, 3-5 4 the run pushes 9 entries, pops 4, and discards none of them. The heavy edges do become stale, but the four light edges at vertex 1 are enough to finish the tree, and the loop stops before any stale entry reaches the top. Staleness costs memory here and no pops at all — which is a different thing from what the preset's name suggests, and the count is what settles it.
The panel prints a column labelled as E times log₂ V for reference. It is computed as the number of edges times the integer part of the base-two logarithm of the number of vertices, so on the opening graph it is 9 times 2, which is 18. The measured comparison count is 12. Those two numbers are not the same kind of thing and the panel says so: the first is a count of something that happened on one graph from one starting vertex, and the second is a scale for what the heap operations would cost in the worst case.
Specifically, 12 being below 18 is not evidence that the algorithm beats its bound, and 24 from vertex 4 being above it is not evidence that it fails one. The reference is a number to compare growth against across several graphs, and the lab's other presets are there to be swept: a star on six vertices gives 12 comparisons against a reference of 10, and the nine-edge graph on five vertices gives 18 against 18. No verdict is printed beside the column, deliberately.
Both algorithms are run on whatever graph you type and the two weights are printed together. On the opening graph both give 19. On the ties preset 1-2 2, 1-3 2, 2-3 2, 3-4 1 both give 5, and here they take the same three edges in different orders: one starts with the edge of weight 1 because it sorted first, the other reaches it last because its tail only joined the tree at the end. Equal weight, equal edge set, different schedule — and on a graph with a genuine choice between tied edges, the edge sets can differ too.
The measured counts, beside the bound. From vertex 1: 9 pushes, 7 pops, 12 comparisons, weight 19. From vertex 4: 9 pushes, 7 pops, 24 comparisons, weight 19. The bound is O(E log V) on every graph from every start, and it comes from at most E pushes and at most E pops, each costing O(log V) comparisons on a heap holding at most E < V² entries. Four starting vertices on one graph is not a bound, and the spread between 12 and 24 is exactly the reason to say so.
Interactive
Lazy deletion instead of decrease-key, so a pop can bring back an edge with nowhere to go
Method
Maintain the boundary, and test every pop before you use it.
The whole algorithm is a question about the boundary of S, and the boundary is cheap to maintain only if membership is a constant-time test. Recomputing which vertices are in the tree from the edge list each step is the change that turns this into a quadratic algorithm without anything looking wrong.
An entry is valid when pushed and may expire before it surfaces. Checking at push time is not enough and deleting from the middle of a heap is not cheap, so the check belongs at the pop. Count the discarded pops: they are real work and they belong in any measurement you report.
The heap returns the lightest edge it currently holds, and it only holds edges whose tails have joined. A heavier edge coming out before a lighter one is normal and is not a defect in the heap; it means the lighter one was not yet a candidate.
The tree does not change and the work does. On the lab's opening graph the comparison count runs from 12 to 24 over four starts. A single measurement presented as the algorithm's cost is a measurement of one start on one graph.
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 and the tree starts at vertex 1.
The stale pop is the third row, and it is worth being precise about why 1-2 expired. It was pushed at the start, when 2 was outside the tree. By the time it reached the top, 2 had been brought in by 2-3 at weight 2 — a lighter edge that did not exist as a candidate until 3 joined. Nothing went wrong; the entry simply stopped describing a crossing edge.
Two entries were never popped at all: 3-4 at 7 and 5-7 at 8 were still in the heap when the sixth edge was taken and the loop stopped. Those are the same two edges the sorted method rejected, reached by a completely different route, and it is a good check on a hand-run that the two methods disagree about nothing but order.
For a faded rehearsal, start the same graph at vertex 4 and predict the first three pops before running it. The supplied first move is this: the edges at 4 are 2-4 at 5, 3-4 at 7 and 4-5 at 1, so the first pop is 4-5. Say what the next two are, whether any pop is stale from this start, and what the final weight is.
You should be able to maintain S and the candidate heap, take the lightest crossing edge each step, recognise and discard an expired entry, name the cut that makes each taken edge safe, and separate the counts that move with the starting vertex from the weight that does not.
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.