(C) Springer Verlag, Lecture Notes on Computer Sience

An Algorithm for Enumerating all Directed Spanning
Trees in a Directed Graph
Takeaki UNO
Department of Systems Science, Tokyo Institute of Technology, 2-12-1 Oh-okayama,
Meguro-ku, Tokyo 152, Japan. uno@is.titech.ac.jp
A directed spanning tree in a directed graph G = (V, A) is a spanning
tree such that no two arcs share their tails. In this paper, we propose an algorithm forlisting all directed spanning trees of G. Its time and space complexities are O(|A| +ND(|V |, |A|)) and O(|A| + DS(|V |, |A|)), where D(|V |, |A|) and DS(|V |, |A|) are the timeand space complexities of the data structure for updating the minimum spanning tree
in an undirected graph with |V | vertices and |A| edges. Here N denotes the number of
directed spanning trees in G.

Abstract:

Keywords directed spanning tree, listing, enumerating algorithm

1

Introduction

Let G = (V, A) be a directed graph with vertex set V and arc set A. An arc is speciﬁedby both of its endpoints. One of them is called its head and the other is called its tail.
A directed spanning tree of G is a spanning tree in which no two arcs share their tails.
Each vertex is the tail of exactly one arc of the directed spanning tree except for a special
vertex r. We call r the root of the spanning tree.
Directed spanning trees have been studied in many ﬁelds. For instance, many problems
on road and telephone networks have been formulated as some optimization problems of
directed spanning trees. Some of them have complicated objective functions, and we canhardly solve them in eﬃcient time. For those problems, one of the most simple approaches
is to use enumerating. The branch-and-bound method, which is one of the most popular
approaches, can be also considered as a kind of enumerating. In this method, the timecomplexity of the enumerating algorithm greatly inﬂuences to its speed. Therefore, improvements of enumerating algorithms largely enhance the eﬃciency for those problems.
In this paper, we consider the problem of enumerating all directed spanning trees withthe root r of the given graph G. This problem has been studied for nearly 20 years. In
1978, H. N. Gabow and E. W. Myers proposed an algorithm which runs in O(|A| + N|A|)
time and O(|A|) space [1]. Here N denotes the number of directed spanning trees in G.
In 1992, H. N. Kapoor and H. Ramesh improved the time complexity to O(|A| + N|V |)1

[2]. Since a directed spanning tree requires O(|V |) time for outputting, it is the optimalalgorithm in the sense of both time and space complexities if we have to output all of them
explicitly. On the other hand, in undirected graphs, compact output methods have beenstudied to shorten the size of outputs [2, 3]. They output a spanning tree by diﬀerencesfrom the previous outputted tree. By outputting all spanning trees in a special order,
we can reduce the total size of outputs to O(N). A. Shioura, A. Tamura and T. Uno
proposed an optimal algorithm with the compact output method for enumerating all
undirected spanning trees [3]. In their algorithm, they utilizes the reverse search. Our
method in this note is also based on this reverse search technique. It can be also considereda kind of the back tracking method, which is used in [2].
Here we propose an algorithm for enumerating all directed spanning trees in O(|A| +ND(|V |, |A|)) time. Our algorithm constructs and preserves an undirected graph with
|V | vertices and at most |A| weighted edges. This graph is modiﬁed after each directedspanning tree is encountered. To update the data structure for ﬁnding new directedspanning trees, we delete, add or change the weight of an edge, and ﬁnd the minimum
spanning tree of the graph in each iteration of the algorithm. Since only few edges arechanged in each iteration, we construct the minimum spanning tree of the changed graphfrom the previous one by some updating spanning tree algorithm.
Therefore the time complexity of our algorithm depends on the time complexity of the
updating algorithm, which is denoted by D(|V |, |A|). The space complexity also depends
on the updating algorithm. We denote its space complexity by DS(|V |, |A|). The update
operations are adding, deleting and changing the weight of an edge. Some data structures are proposed for these updating operations of the minimum spanning tree. G. N.
Frederickson proposed an O(|A|1/2 ) time data structure [5], and D. Eppstein, Z. Galil, G.
F. Italiano and A. Nissenzweig improved the time complexity into O(|V |1/2 log(|A|/|V |))[4]. Their time complexities are smaller than O(|V |). There use only O(|A|) space, thus
we do not lose the optimality of space complexity by our improvement.

2

The Reverse Search and the Parent-Child RelationshipWe use a technique called reverse search for enumeration problems. The reverse searchrequires a parent-child relationship on those objects to be enumerated. The relationshiphas to satisfy: i) each object except for a speciﬁed object r0 has a parent object and ii)
each object is not a proper ancestor of itself.
Let us consider the graph representation of this parent-child relationship. An object
corresponds to a node v of the graph and an edge (v, u) is included in the graph if and only
if u corresponds to its parent. By the condition of the relationship, the graph contains nocycle and forms a rooted spanning tree. This tree is called an enumeration tree. In Figure
1, we show an example of an enumeration tree. The reverse search traverses all nodes
2

0

2

3

1

Fig1: The enumeration tree. The emphasized line of the graph is T0.

of the enumeration tree by some depth-ﬁrst-search scheme from the speciﬁed object r0.
Even if the size of the enumeration tree is huge, only a small memory space is required,since we can traverse it by only ﬁnding the parent and all children of the current object.
Hence an important point in speeding up reverse search is “How to enumerate all children
eﬃciently fast.”
To enumerate all directed spanning trees, we deﬁne a parent-child relationship among
them as below. Let T0 be a depth-ﬁrst-search tree of the given graph G. A depthﬁrst-search tree is a directed spanning tree which arises from the traversal route of adepth-ﬁrst-search. We assume that any search traverses an arc from its head to tail.
Using this speciﬁed directed tree T0, we introduce the parent-child relationship. In therelationship, T0 corresponds to the speciﬁed object r0 . Let the indices of the vertices of G
be as the order of the traversal of the depth ﬁrst search. Similarly, we deﬁne the indicesof arcs of G by indices of their tails. The parent of a directed spanning tree Tc = T0 is
deﬁned by the directed spanning tree Tp = Tc \ f ∪ e where e is the minimum index arc
e in T0 \ Tc and f is the arc of Tc sharing its tail with e. Since f shares its tail only one
arc of Tc , Tp is uniquely deﬁned. From the deﬁnition of the index, there always exists apath from the root to the head of e. Hence e is not contained in any cycle and Tp forms
a directed spanning tree. In this parent-child relationship, Tc is not a proper ancestor of
itself, as Tp contains just one more arc of T0 than Tc .
3

To output directed spanning trees compactly, we consider diﬀerences between a directed spanning tree and the one outputted just before by the reverse search. Some ofthem may have O(|V |) diﬀerences, but the total diﬀerences over all directed spanning
trees does not reach O(|V |N ). Since the reverse search traverses the enumeration tree by
the depth-ﬁrst-search, the total amount is twice the sum of diﬀerences between a childand its parent over all directed spanning trees. Any directed spanning tree diﬀers by only
two arcs from its parent, thus the total the size of outputs can be reduced into O(N) by
outputting only diﬀerences.
Next we show the method of enumerating all children of a directed spanning tree Tp.
Let v ∗ (Tp) be the minimum index among arcs in T0 \ Tp . Exceptionally, we deﬁne v ∗ (T0)by ∞. Let us construct Tc by removing an arc e from Tp whose index is less than v ∗(Tp )and adding an arc f = e sharing its tail with e. If Tc forms a tree, it is a child of Tp fromthe deﬁnition. Conversely, in the case that Tp = Tc \ f ∪ e is the parent of Tc , the index ofe is less than v ∗(Tp ). Thus all children of Tp can be found by the above method. To ﬁnd
children, we deal with only vertices and arcs whose indices are less than v ∗(Tp). Hence
we call them valid.
For a tree T , we call an arc not in T a back-arc, if its tail is an ancestor of its head, andotherwise a non-back-arc. In the above method, if f is a back-arc of Tp, then Tc = Tp \e∪fcontains a cycle and is not a directed spanning tree. If f is a non-back-arc of Tp, there
always exists a path from r to the head of f in Tc and Tc contains no cycle. Hence eachchild of Tp is obtained by adding a valid non-back-arc f and removing an arc e sharing its
tail with f. Valid non-back-arcs have a one-to-one correspondence with the children andthe number of children is same as the number of valid non-back-arcs. By maintaining theset of all valid non-back-arcs, ﬁnding all children can be accomplished suﬃciently easily.
We now describe the framework of our algorithm.
ALGORITHM: Enum Directed Spanning Trees(G)Step 1: Find T0 by a depth-ﬁrst-search.
Step 2: Assign indices for each vertex.
Step 3: Classify arcs not in T0 into the back-arc set and the non-back-arc set.
Sort them in order of their indices.
Step 4: Call Enum Directed Spanning Trees Iter(T0).

ALGORITHM: Enum Directed Spanning Trees Iter(Tp)
Step 1: For each valid non-back-arc f of Tp, do the following.
Step 2: Construct Tc by adding f and removing an arc e.
Output it by the diﬀerence from the previous outputted one.
Step 3: List all valid non-back-arcs of Tc in order of their indices.
Step 4: Call Enum Directed Spanning Trees(Tc ) recursively.

4

Step 1 to 3 of the algorithm Enum Directed Spanning Trees(G) runs in O(|A|)
time. The construction of a child of Tp in Step 2 of Enum Directed Spanning Trees Iter
may be done in O(1) by swapping two arcs. Step 3 lists all valid non-back-arcs of Tc ,and the number of them is equal to the number of children of Tc in the enumeration tree.
Thus total time spent until Step 3 is the time to ﬁnd one valid non-back-arc of Tc per one
outputted directed tree.
The earlier algorithm [2] takes O(|V |) time for ﬁnding one non-back-arc in the worst
case and it is the bottle neck of the time complexity while other parts of the algorithm
take only O(1) time. Our improvement on this part reduces its time complexity to thetime necessary to update the minimum spanning tree of an undirected graph. In the next
section, we show a data structure which is the key to the improvement.

3

An Improved Data Structure

To enumerate all valid non-back-arcs suﬃciently fast in Step 3, we show the following
two conditions. They are also stated in [2]. We denote the tail of e by v and the nearest
common ancestor of v and the head of f by w.
Lemma 1 Let Tc = Tp \ e ∪ f be a child of Tp . A valid non-back-arc of Tp is a valid
non-back-arc of Tc if its index is less than v ∗(Tc ).
Proof : Since T0 is a depth-ﬁrst-search tree, the index of the tail of f is larger thanv ∗(Tc ). Thus for all valid vertices of Tc , all its descendants in Tc are also descendants Tp.
Therefore any valid vertex is not an ancestor of a vertex v in Tc if it is not an ancestor inTp .
Lemma 2 Let P be the vertex set of the interior points of the path from the head of e
to w on Tp , where interior points of the path are vertices of the path which are not its
endpoints. A back-arc of Tp is a non-back-arc of Tc if and only if its head is a descendantof v and its tail is in P .
Proof : A descendant of v is also a descendant of all vertices of P but not in Tc . Thus if
the head of a back-arc is a descendant of v and its tail is in P , it is a non-back-arc of Tc .
Conversely, only descendants of v have ancestors which are not ancestors in Tc and only
vertices of P have descendants which are not descendants in Tc . Thus any back-arc of Tp
has the head in descendants of v and a tail in P if it is a non-back-arc of Tc .
From these lemmas, the valid non-back-arc set of Tc is composed by those back-arcs
of Tp and valid non-back-arcs of Tp whose indices are less than v ∗(Tc ). By listing both ofthem in order of their indices, we can obtain the non-back-arc set sorted by their indices.
The former can be listed easily if we have the set of valid non-back-arcs of Tp sorted by
5

e

f

f

f

Fig2: The way of B(T ) changes.

their indices. But the latter is hard to list with only simple data structures. We use thefollowing data structure shown as below.
For a directed spanning tree Tp , let B(Tp) be an undirected graph with vertex set V
and edge set composed by arcs of Tp, valid back-arcs of Tp and some of other rest backarcs. B(T0) is an undirected graph composed by T0 and all of its back-arcs. The weightof edges in the graph B(Tp) is deﬁned as 0 for arcs of Tp and (|V | + 1 − index ) for others.
The minimum spanning tree of B(Tp) is Tp.
By removing a valid arc e of Tp from the undirected graph B(Tp), the minimum
spanning tree of B(Tp) is split into two. One of them contains all descendants of v andthe other contains the rest. The minimum spanning tree of the graph B(Tp)\e is obtainedby adding the minimum weight cut edge b, which has endpoints in both of those two trees.
From above lemmas, b is a valid non-back-arc of Tc if and only if the tail of b is in P .
In the case that b does not exist, no back-arc of Tp is a non-back-arc of Tc . Since b is aback-arc of Tp, the tail of b is in the path from v to r and its head is a descendant of v.
From the deﬁnition of the weight, no back-arc connects a descendant of v and an interior
point of the path from the tail of b to v. We show an example of the way of B(T ) changes
in Figure 2. Emphasized lines are a part of the minimum spanning tree. Doted lines are
eliminated and a new edge will be inserted.
Therefore we can ﬁnd a new valid non-back-arc of Tc by updating the minimum spanning tree. By removing b and applying the method repeatedly, we can enumerate all
new valid non-back-arcs of Tc . The algorithm is showed as follows. It outputs all new
non-back-arcs and updates the graph from B(Tp) to B(Tc ).
ALGORITHM: Enum Non-back-arcs(T p, B(Tp), e, f)
Step 1: Remove e from B(Tp).
Step 2: Update the minimum spanning tree by adding some edge b.
If b does not exist, then add f to B(Tp), and stop.
6

Step 3: If b is not a back-arc of Tc = Tp \ e ∪ f, then remove b and add f to B(Tp). Stop.
Step 4: Output b. Remove b from B(Tp). Go to Step 2
Lemma 3 The algorithm Enum Non-back-arcs outputs all back-arcs of Tp which arevalid non-back-arcs of Tc in the order of their indices. It takes O(D(|V |, |A|)) time andO(D(|V |, |A|)) time for one output. Its space complexity is O(|A| + DS(|V |, |A|)).
Proof : Since the algorithm ﬁnds the maximum index one among those back-arcs, backarcs are outputted in the order of their indices. Therefore merging operation is done inlinear time of the number of non-back-arcs. To identify both the endpoints of the path
P , we have to ﬁnd the nearest common ancestor of the head of e and the head of f. It
can be found in O(log |V |) time by D. D. Slater and R. E. Tarjan’s dynamic tree data
structure [6]. The updating operation, which is adding an edge, deleting an edge andchanging the root, of it is also done in O(log |V |) time. The time complexity of the restof the algorithm is O(D(|V |, |A|)) for one iteration. Because of the number of iterations,the time complexity is O(D(|V |, |A|)) per one output.
By using this algorithm, we obtain the following theorem.
Theorem 3.1 Algorithm Enum Directed Spanning Trees enumerates all directedspanning trees in O(|A| + ND(|V |, |A|)) time. It uses O(|A| + DS(|V |, |A|)) space.
Proof : By above lemmas, the time complexity of algorithm is O(|A|) for preprocessing,O(log |V | + D(|V |, |A|)) time for one directed spanning tree and O(D(|V |, |A|)) time for
one new non-back-arc. Thus the time complexity satisﬁes the condition. The algorithm
changes the data structure for updating the minimum spanning tree if a recursive calloccurs. When the recursive call ends, we have to restore it. The restoring operation
is done by adding the deleted edge, deleting the added edge and changing the modiﬁed
weight. The total amount of these changes may increase by recursive calls, but the total
size of each of the added edges, deleted edges and weight changed edges does not exceed|A|. Therefore they are stored in O(|A|) space.
The set of valid non-back-arcs and back-arcs are treated similarly. After a recursive
call, we can restore them by adding and removing the removed or added arcs. The total
space for storing them is O(|A|). Hence the space complexity is O(|A| + DS(|V |, |A|)).

Acknowledgment
We greatly thank to Associate Professor Akihisa Tamura of University of ElectroCommunications for his kindly advise. We also owe a special debt of gratitude of Research
Assistant Yoshiko T. Ikebe of Science University of Tokyo.

7

References[1] H. N. Gabow, E. W. Myers, “Finding All Spanning Trees of Directed and Undirected
Graphs,” SIAM J. Comp., 7, 280-287, 1978.
[2] H. N. Kapoor and H. Ramesh, “Algorithms for Generating All Spanning Trees of
Undirected, Directed and Weighted Graphs,” Lecture Notes in Computer Science,
Springer-Verlag, 461-472, 1992.
[3] A. Shioura, A. Tamura and T. Uno, “An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs, ” SIAM J. Comp., to be appeared.
[4] D. Eppstein, Z. Galil, G. F. Italiano and A. Nissenzweig, “Sparsiﬁcation - A Technique for Speeding up Dynamic Graph Algorithms, ” FOCS 33, 60-69, 1992.
[5] G. N. Fredrickson, “Data Structure for On-line Updating of Minimum Spanning
Trees, with Applications, ” SIAM J. Comp., 14, No 4, 781-798, 1985.
[6] D. D. Sleator and R. E. Tarjan, “A Data Structure for Dynamic Trees,” J. Comp.
Sys. Sci. 26, 362-391, 1983.
[7] R. E. Tarjan, “Depth-First Search and Linear Graph Algorithm,” SIAM J. Comp. 1,
146-169, 1972.

8