An algorithm for enumerating all spanning trees of a directed graph

We present an O(NV + V-3) ti, algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O(NE V + E) [1] when V-2 = o(N), which will be true for most graphs. Here, N ref ers to the number of spanning trees of a graph having V vertices and E edge s, The algorithm is based on the technique of obtaining one spanning tree f rom another by a series of edge swaps. This result complements the result i n the companion paper [3] which enumerates all spanning trees in an undirec ted graph in O(N + V + E) time.