Finding All Spanning Trees of Directed and Undirected Graphs

Abstract

An algorithm for finding all spanning trees (arborescences) of a directed graph is presented. It uses backtracking and a method for detecting bridges based on depth-first search. The time required is $O(V + E + EN)$ and the space is $O(V + E)$, where V, E, and N represent the number of vertices, edges, and spanning trees, respectively. If the graph is undirected, the time decreases to $O(V + E + VN)$, which is optimal to within a constant factor. The previously best-known algorithm for undirected graphs requires time $O(V + E + EN)$.