Research and Advances

Algorithm 422: minimal spanning tree [H]

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.

Advertisement

Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved