Algorithms forenumerating all spanning trees of undirected and weighted graphs

Abstract

In this paper, we present algorithms for enumeration of spanning trees in undirected graphs, with and without weights. The algorithms use a search tree technique to construct a computation tree. The computation tree can be used to output all spanning trees by outputting only relative changes between spanning trees rather than the entire spanning trees themselves. Both the construction of the computation tree and the listing of the trees is shown to require $O(N + V + E)$ operations for the case of undirected graphs without weights. The basic algorithm is based on swapping edges in a fundamental cycle. For the case of weighted graphs (undirected), we show that the nodes of the computation tree of spanning trees can be sorted in increasing order of weight, in $O(N \log V + V E)$ time. The spanning trees themselves can be listed in $O(NV)$ time. Here N, V, and E refer, respectively, to the number of spanning trees, vertices and edges of the graph.