Abstract
Let G = (V, E) be a directed graph with vertex set V and edge set E. A directed spanning tree of G rooted at a vertex r is a spanning tree of G having a unique path from r to every other vertex. In this thesis, by using Kapoor and Ramesh’s [8] “edge-exchange” technique, we propose an O(Nnlogn + n^2 + nm) time algorithm for enumerating all spanning trees of a directed graph. The output size of our algorithm is O(N + n^2) that is the same as Kapoor and Ramesh’s algorithm in [8]. Furthermore, although our algorithm is slightly slower than Kapoor and Ramesh’s, the space complexity of our algorithm is O(n + m), which is optimal.