3 / 3 Minimum Spanning Trees

Both Ends Already In

Lazy Prim. scan(v) marks v and pushes every edge from v whose other endpoint is unmarked.

scan(A);
while (!pq.isEmpty()) {
    Edge e = pq.delMin();
    int v = e.either(), w = e.other(v);
    mst.add(e);
    weight += e.weight();
    if (!marked[v]) scan(v);
    if (!marked[w]) scan(w);
}

Run it on the triangle A-B 1, A-C 2, B-C 3. The correct MST is 2 edges of total weight 3. What does this report?

A

2 edges, total weight 4, taking A-B and B-C.

B

3 edges, total weight 6. The line if (marked[v] && marked[w]) continue; is missing, so B-C is added even though B and C are both already in the tree, and the result is not a tree at all.

C

2 edges, total weight 3, which is correct. Leaving ineligible edges on the queue is what "lazy" means, so no check is required.

D

It loops forever, because B-C is pushed again every time it is popped.