Finding a Minimum Spanning Tree in a Graph

A minimum spanning tree of a weighted connected graph is a subgraph containing all of the vertices of the original graph (i.e., it spans the the original graph), and a subset of the edges, so that the subgraph is also connected and the total of the edge weights is as small as possible. A minimum spanning tree need not be unique, but if it is, then the starting vertex does not matter.

Note that it is called a minimum spanning tree, not a minimum spanning graph. Why do you suppose this is?

The following diagram shows a "spanning tree" that is not the minimum spanning tree, as well as the minimum spanning tree, for a small graph.

A greedy algorithm for the solution to any problem is one that makes the best decision based on "local" information (rather than "global" information). It is somewhat rare for a greedy algorithm to give the overall optimal solution to a problem, but that is exactly how the algorithm shown below (for finding a minimum spanning tree, and due to Dijkstra and Prim) works.

Note, in thinking about the algorithm, that we consider each vertex of the graph to lie in one of the following three categories:

1. in the Minimum Spanning Tree
2. on the fringe of the Minimum Spanning Tree (the "fringe is the set of vertices adjacent to the vertices in Minimum Spanning Tree but not in the Minimum Spanning Tree)
3. not yet considered

Algorithm FindMinimumSpanningTree
---------------------------------
Select a starting vertex
Build initial fringe of all vertices adjacent to starting vertex
while there are vertices not yet considered
    Find "fringe edge" having smallest weight
    Add associated vertex to the MST
    Update fringe as follows:
        Add to fringe all vertices connected to new vertex
        Update edges to fringe vertices so they contain smallest weights