Minimum spanning tree

<< Click to Display Table of Contents >>

Navigation:  Network and Location Analysis > Network Construction, Optimal Routes and Optimal Tours >

Minimum spanning tree

Given a set of vertices (points, nodes) an enormous number of possible interconnections may be made to produce a network of direct or indirect connections between vertices. The set of connections that minimizes total edge length whilst ensuring every point is reachable from every other point is known as a minimal spanning tree (MST). There is an exact solution to this problem. The algorithm involves a construction or growth process as follows: (i) connect every point to its nearest neighbor — typically this will result in a collection of unconnected sub-networks; (ii) connect each sub-network to its nearest neighbor sub-network; (iii) iterate step (ii) until every sub-network is inter-connected. This process (which is basically Prim’s algorithm described in Section 7.2.2, Heuristic and meta-heuristic algorithms), is illustrated below, with the stages of nearest neighbor linkage identified by numerical sequence values.

The MST for a set of vertices can be computed in O(nlogn) time so is in the class P. An interesting feature of the solution is that it is a subset of various other more connected forms of network including the Delaunay triangulation — see Cheriton and Tarjan (1976) and Arora (1996) for more details. Some packages (e.g. the LEDA code suite from Algorithmic Solutions) first compute the Delaunay triangulation of the point set, then generate the Delaunay diagram if necessary (a subset of the triangulation in some instances) and run the minimum spanning tree algorithm on this graph, systematically deleting edges that do not belong to the MST. Note that whilst the MST provides the shortest possible connection between all vertices, it is very susceptible to disruption since deleting any link (e.g. link failure, road accident) will result in loss of overall connectivity.

Figure 7‑4 Minimum Spanning Tree

A. Point set (nodes or vertices)