Two Algorithms for Generating Weighted Spanning Trees in Order

Two algorithms for generating spanning trees of a connected graph in order of increasing weight are presented. The first generates the K smallest weight trees, where K can be specified in advance or during execution of the algorithm. The run time is O (KE (E, V) + E E) and the space is O (K + E) ; here V is the number of vertices, E is the number of edges, and is Tarjan’s inverse of Ackermann’s function and is very slow-growing. The algorithm uses a minimum weight spanning tree as a “reference tree”, and exchanges edges to derive other trees. The second algorithm, a modification of the first, generates all spanning trees of the graph, in order. If N is the number of spanning trees, the time is O (NE) and the space is O (N+E).