networks2

 Minimum Spanning Tree Problem

A spanning tree connects all of the nodes in a graph and has no cycles.  There are numerous ways to select connecting arcs to create a spanning tree.  A minimum spanning tree is a spanning tree that has the shortest total length of connecting arcs. It may not be unique.

In the graph below, the arcs are labeled with distances between the nodes that they are connecting. The animation demonstrates Prim's Algorithm for finding a minimum spanning tree.