Home → Magazine Archive → April 1972 (Vol. 15, No. 4) → Algorithm 422: minimal spanning tree [H] → Abstract

Algorithm 422: minimal spanning tree [H]

By V. Kevin M. Whitney

Communications of the ACM, Vol. 15 No. 4, Pages 273-274

This algorithm generates a spanning tree of minimal total edge length for an undirected graph specified by an array of inter-node edge lengths using a technique suggested by Dijkstra [1]. Execution time is proportional to the square of the number of nodes of the graph; a minimal spanning tree for a graph of 50 nodes is generated in 0.1 seconds on an IBM System 360/67. Previous algorithms [2, 3, 4, 5] require an amount of computation which depends on the graph topology and edge lengths and are best suited to graphs with few edges.

The full text of this article is premium content


No entries found