CISC 235 Lecture Notes - Lecture 20: Minimum Spanning Tree, Binary Heap, Prims

• School: Queen's University
• Department: Computing
• Course: CISC 235
• Professor: Robin W Dawes

Document Summary

The generic minimum spanning tree algorithm looks like this: Call a set of edges a safe if there is a mst containing a. Start with a safe set of edges a while |a| < n: choose an edge e such that a+{e} is safe. The key to any mst algorithm is efficiently and correctly choosing the next edge e to add to the mst. Prim"s algorithm starts with a single vertex and expands the mst by repeatedly choosing the least-weight edge that joins a vertex in the tree to a vertex not yet in the tree. Note that a graph may have more than one mst. Prim"s algorithm is guaranteed to find one of them. We assume that g is a connected graph. def prim_mst(): M = {} # m will be a list of edges that form the minimum.