Lecture 12 - Notes

February 18, 2016

Minimum Weight Spanning Trees Continued

Prim's Algorithm

• Lazy: Keep track of edges in cut
• Eager: Keep track of vertices not in tree

Indexed Priority Queues

For the eager algorithm, we implement it with a binary queue. We maintain the arrays,

• keys[i] is th priority of i
• pq[i] is the index of the key in heap position i
• qp[i] is the heap position of the key with index i