Consider the undirected network as shown in
the figure. The graph consists of nodes and edges, and each
edge has an associated length. An edge is the line segment connecting
two nodes and has the same length in either direction.
The Minimal Spanning Tree problem is to select a set
of edges so that there is a path between each node. The
sum of the edge lengths is to be minimized.
When the edge lengths are all nonnegative, as
assumed here, the optimum selection of edges forms a spanning
tree. Because of this characteristic of the solution, the problem
is called the minimum spanning tree problem. The problem can
be solved with a greedy algorithm called Prim's Algorithm. Click
the link below to see the statement of the algorithm and a demonstration.
The algorithm is one of the simplest in optimization
theory. The optimum is found after m -1 performances
of the selection step, where m is the number of nodes.