6.4 MINIMUM SPANNING TREE ALGORITHM 155
6.4 Minimum Spanning Tree Algorithm
The minimum spanning tree (MST) of a weighted connected graph is a sub-
graph that contains all of the nodes of the original and a subset of the edges so
that the subgraph is connected and the total of the edge weights is the smallest
possible. If the original graph is not connected, the processes below can be
used on each of the separate components to produce a spanning tree for each
one.
There is a brute force way that the MST could be found for a connected
graph. Because the edges in the MST are a subset of the edges in the entire
graph, we could look at all of the possible subsets of the edge set until we find
the MST. You should see that this is a very time-consuming process. First, if
there are N edges, there would be 2N subsets. For each of these subsets, we
would need to first check that it spans all of the nodes and has no cycles. Then
we could calculate its total weights. We could speed up the process once we
find the first spanning tree. Any edge subset with a total weight that is greater
than that of our current best spanning tree can’t possibly be better, so there is
no need to check to see if it spans all of the nodes and is acyclic. Even with this
improvement, this brute force method would be of order O(2N).
■ 6.4.1 The Dijkstra-Prim Algorithm
The following algorithm to find the MST was developed by Edsger Dijkstra
and R. C. Prim in the late 1950s; they worked and published their results
independently.
To find the MST, we will use what is called a “greedy” algorithm. Greedy
algorithms work by looking at a subset of the larger problem and making the
best decision based on that information. In this case, we will, at each step of
the process, look at a collection of potential edges to add to the spanning tree
and pick the one with the smallest weight. By doing this repeatedly, we will
grow a spanning tree that has a minimum overall total.
To accomplish this process, we will consider the nodes of the graph to be in
one of three categories: in the tree, on the fringe of the tree, and not yet con-
sidered. We begin by picking one node of the graph and putting that into the
spanning tree. Because our result is an unrooted tree, the choice of an initial
node has no impact on our final result (unless there are multiple MSTs). We
then place all of the nodes that are connected to this initial one into the fringe
