Portal de Periódicos da CAPES

Algorithm 422: minimal spanning tree [H]

1972; Association for Computing Machinery; Volume: 15; Issue: 4 Linguagem: Inglês

10.1145/361284.361299

1557-7317

V. Kevin M. Whitney,

Graph Theory and Algorithms

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.