Prim module¶

Prim’s algorithm for minimum spanning trees. Given a starting vertex, create a cloud of vertices VT and then find the edge of minimum weight such that one end is in VT and the other end is not. Repeat until the tree has n - 1 edges.

Algorithm 5.4.2 on page 82, using a heap to store vertices

Prim.prim(G)¶

Perform Prim’s algorithm for a minimum spanning tree.

This version of Prims will ALWAYS start a vertex 0

Parameters

Gnx.Graph

The graph we want to find a minimum spanning tree in

Returns

nx.Graph

A minimum spanning tree for G.