Algorithms For Dummies

  Reconnecting the Dots 

     183

Reducing to a Minimum Spanning Tree

Many problems that algorithms solve rely on defining a minimum of resources to 

use, such as defining an economical way to reach all the points on a map. This 

problem was paramount in the late nineteenth and early twentieth centuries when 

railway and electricity networks started appearing in many countries, revolution-

izing  transportation  and  ways  of  living.  Using  private  companies  to  build  such 

networks was expensive (it took a lot of time and workers). Using less material 

and a smaller workforce offered savings by reducing redundant connections.

Some redundancy is desirable in critical transportation or energy networks even 

when striving for economical solutions. Otherwise, if only one method connects 

the network, it’s easily disrupted accidentally or by a voluntary act (such as an act 

of war), interrupting services to many customers.

In Moravia, the eastern part of Czech Republic, the Czech mathematician Otakar 

Borůvka found a solution in 1926 that allows constructing an electrical network 

using the least amount of wire possible. His solution is quite efficient because it 

not only allows finding  a way to connect  all the towns  in Moravia in the most 

economical way possible, but it had a time complexity of O(m*log n), where m is 

the number of edges (the electrical cable) and n the number of vertexes (the 

towns). Others have improved Borůvka’s solution since then. (In fact, algorithm 

experts partially forgot and then rediscovered it.) Even though the algorithms you 

find in books are better designed and easier to grasp (those from Prim and Krus-

kal), they don’t achieve better results in terms of time complexity.

A minimal spanning tree defines the problem of finding the most economical way 

to accomplish a task. A spanning tree is the list of edges required to connect all the 

vertexes in an undirected graph. A single graph could contain multiple spanning 

trees, depending on the graph arrangement, and determining how many trees it 

contains is a complex issue. Each path you can take from start to completion in a 

graph is another spanning tree. The spanning tree visits each vertex only once; it 

doesn’t loop or do anything to repeat path elements.

When you work on an unweighted graph, the spanning trees are the same length. 

In unweighted graphs, all edges have the same length, and the order you visit 

them in doesn’t matter because the run path is always the same. All possible 

spanning trees have the same number of edges, n-1 edges (n is the number of 

vertexes), of the same exact length. Moreover, any graph traversal algorithm, 

such as BFS or DFS, suffices to find one of the possible spanning trees.

Things become tricky when working with a weighted graph with edges of differ-

ent lengths. In this case, of the many possible spanning trees, a few, or just one, 

have the minimum length possible. A minimum spanning tree is the one spanning 

---

184