An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs.
Let G be an undirected graph with V vertices and E edges. Many algorithms have been developed for enumerating all spanning trees in G. Most of the early algorithms use a technique called "backtracking." Recently, several algorithms using a different technique have been proposed by Kapoor and Ramesh (1992), Matsui (1993), and Shioura and Tamura (1993). They find a new spanning tree by exchanging one edge of a current one. This technique has the merit of enabling us to compress the whole output of all spanning trees by outputting only relative changes of edges. Kapoor and Ramesh first proposed an O(N E)-time algorithm by adopting such a "compact" output, where N is the number of spanning trees. Another algorithm with the same time complexity was constructed by Shioura and Tamura. These are optimal in the sense of time complexity but not in terms of space complexity because they take O(VE) space. We refine Shioura and Tamura's algorithm and decrease the space complexity from O(VE) to O(V E) while preserving the time complexity. Therefore, our algorithm is optimal in the sense of both time and space complexities.
Introduction
.
Let G be an undirected graph with V vertices and E edges. A spanning tree of G is
defined as a connected subgraph of G which contains all vertices, but no cycle. In this paper
we consider the enumeration of all spanning trees in an undirected graph. Many algorithms
for solving this problem have been developed, e.g. [7, 8, 4, 5, 6, 9], and these may be divided
into several types.
3 Department of Information Sciences, Tokyo Institute of Technology, 2-12-1 Oh-okayama, Meguro-ku,
Tokyo 152, Japan. shioura@is.titech.ac.jp
y Department of Computer Science and Information Mathematics, The University of Electro-
Communications, 1-5-1 Chofugaoka, Chofu-shi, Tokyo 182, Japan. tamura@im.uec.ac.jp
z Department of Information Sciences, Tokyo Institute of Technology, 2-12-1 Oh-okayama, Meguro-ku,
Tokyo 152, Japan. uno@is.titech.ac.jp
The first type [7, 8, 4], to which belong many of the early algorithms use a technique
called 'backtracking'. This is a useful technique for listing the kinds of subgraphs, e.g. cycles,
paths, and so on. Gabow and Myers [4] refined Minty's algorithm [7] and Read and Tarjan's
[8]. Their algorithm uses O(NV +V +E) time and O(V +E) space, where N is the number
of all spanning trees. If we enumerate all spanning trees by outputting all edges of each
spanning tree, their algorithm is optimal in terms of time and space complexities.
Recently, several algorithms [5, 6, 9] which use another technique have been developed.
These algorithms find a new spanning tree by exchanging one pair of edges, instead of
backtracking. Furthermore, if we enumerate all spanning trees by outputting only relative
changes of edges between spanning trees, we can compress the size of output to 2(N+V ),
and hence, total time complexity may be reduced. In fact, Kapoor and Ramesh [5] proposed
an O(N+V +E) time and O(V E) space algorithm by adopting such a 'compact' output,
which is optimal in the sense of time complexity. On the other hand, Matsui [6] developed
an O(NV +V +E) time and O(V +E) space algorithm for enumerating all spanning trees
explicitly, by applying the reverse search scheme [3]. Reverse search is a scheme for general
enumeration problems (see [1], [2]). Shioura and Tamura [9] also developed an algorithm
generating a compact output with the same time and space complexities as the Kapoor-
Ramesh algorithm, by using the reverse search technique. The Kapoor-Ramesh algorithm,
and the Shioura-Tamura algorithm, however, are not efficient in terms of space complexity,
because they take O(V E) space.
The main aim of this paper is to obtain an algorithm which generates a compact output,
and is optimal in the sense of both time and space complexities, by refining the Shioura-
Tamura algorithm. When the process goes to a lower level node of the computation tree
of the original algorithm, some edge set can be efficiently divided without requiring extra
information. However, in order to efficiently restore such an edge set when the process goes
back to the higher level node, the algorithm requires extra O(E) information. Since the
depth of the computation tree is V 01, it takes O(V E) space. We propose a useful property
for efficiently restoring the edge set and a technique for restoring it which uses extra O(V )
space in all, while time complexity remains O(N+V +E):
In Section 2, we explain the technique for enumeration of spanning trees and compact
outputs. In Section 3, we define a nice child-parent relation between spanning trees and
propose a naive algorithm. In Section 4, we show some properties which are useful for
efficient manipulation of data structures in our implementation. Our implementation is
G

Figure

1: graph G 1 and graph
presented in Section 5, and the time and space complexities are analyzed.
Compact output.
Let G be an undirected graph (not necessary simple) with V vertices
We define two types of edge-sets which are necessary for our
algorithm, so-called fundamental cuts and fundamental cycles. Let T be a spanning tree of
G: Throughout this paper, we represent a spanning tree by its edge-set of size V 01: For
any edge deletion of f from T yields two connected components. The fundamental
cut associated with T and f is defined as the set of edges connecting these components,
and is denoted by Cut(Tnf): Likewise, we define the fundamental cycle associated with
T and as the set of edges contained in the unique cycle of T [ g: We will denote
it as Cyc(T[g): From definition, Tnf[g is a spanning tree for any f 2 T and any
Similarly, for any g 62 T and any f 2 Cyc(T[g); T[gnf is also a
spanning tree. These properties are useful for enumerating spanning trees, because by using
fundamental cuts or cycles we can construct a different spanning tree from a given one by
exchanging exactly one edge.
Given a graph G; let S(G)=(T ; A) be the graph whose vertex-set T is the set of all
spanning trees of G and whose edge-set A consists of all pairs of spanning trees which
are obtained from each other by exchanging exactly one edge using some fundamental cut
or cycle. For example, the graph S(G 1 ) of the left one G 1 is shown in Figure 1.
Our algorithm finds all spanning trees of G by implicitly traversing some spanning tree
D of S(G): In order to output all (V 01) edges of each spanning tree, 2(jT j1V
time is required. However, if we output all edges of the first spanning tree, and then only
the sequence of exchanged edge-pairs of G obtained by traversing D; we need only
exactly two edges of G are
exchanged for each edge of D: Furthermore, by scanning such a 'compact' output, one can
construct all spanning trees. Since we adopt such a compact output, it becomes desirable to
find the next spanning tree from a current one efficiently in constant time.
3 Basic ideas and naive algorithm.
In this section we explain the basic ideas and the naive algorithm.
We define the total orders over the vertex-set fv and the edge-set
of G by their indices as Especially, we
call the smallest vertex v 1 the root. For each edge e; we call the smaller incident vertex
the tail, denoted by @ call the larger one the head, denoted by @ 0 e: Relative to a
spanning tree T of G; if the unique path in T from vertex v to the root v 1 contains
a vertex u then u is called an ancestor of v and v is a descendant of u: Similarly,
for two edges e and f in T; we call e an ancestor of f and f a descendant of e if
the unique path in T from f to the root v 1 contains e: A 'depth-first spanning' tree
of G is a spanning tree which is found by some depth-first search of G: It is known that a
depth-first spanning tree is defined as a spanning tree such that for each edge of G; its one
incidence vertex is an ancestor of the other.
In our algorithm, we make several assumptions for the vertex-set and the edge-set of G:
Assumption (1). T 0 is a depth-first spanning tree of G:
Assumption (2). T 0 =fe
Assumption (3). Any edge in T 0 is smaller than its proper descendants.
Assumption (4). Each vertex v is smaller than its proper descendants relative to
Assumption (5). For any two edges
e 6

Figure

2: graph G 2
Vertices and edges of graph G 2 in Figure 2 satisfy these assumptions. In fact, one can
find T 0 and sort vertices and edges of G in O(V +E) time so that G satisfies the above
assumptions by applying Tarjan's depth-first search [10]. We note that assumptions (1),
(2), and (3) are sufficient for the correctness of our algorithm. We, however, need further
assumptions (4) and (5) for an efficient implementation.
For any nonempty subset S of denotes the smallest edge in S:
For convenience, we assume that
Lemma 3.1. [9] Under assumptions (1) and (3), for any spanning tree T c 6= T
contains exactly one edge.
Proof. The set T 0 n f has exactly two components, one containing @ 0 f and the other
Therefore the unique path Cyc(T c [f) n f from @ 0 f to @ contains at
least one edge in Cut(T 0 nf
Since T 0 is a depth-first spanning tree, we may assume the head of any edge is a
descendant of its tail relative to T 0 ; without loss of generality. Let e be the first edge
from @ 0 f on the path such that e 2 Cut(T 0 nf): Then the head @ 0 e is a descendant of
and the tail @ + e is an ancestor of @ assumption (3) and
the minimality of f; @ are connected in T c " there is no edge
contained in Cut(T 0 nf in the path Cyc(T c [f) n f: Hence e is
the only edge in Cyc(T c [f) n f and Cut(T 0 nf):
Consider the graph G 2 of Figure 2. Here let T
Figure

3: child-parent relations in
In graph G 2 ;
Therefore, Cyc(T c [f) " Cut(T 0 nf)
Given a spanning tree T c 6= T 0 and the edge be the unique
edge in Cyc(T c [f) " Cut(T 0 nf) n f: Clearly, T [fng is a spanning tree. We call
T p the parent of T c and T c a child of T 3.1 guarantees that each spanning
tree other than T 0 has a unique parent. Since jT
the ancestor of all spanning trees. For the graph G 1 in Figure 1, all child-parent pairs are
shown by the arrows in Figure 3. Each arrow goes from a child to its parent. We can see
that all arrows construct a spanning tree of S(G 1 ) rooted at
Let D be the spanning tree of S(G) consisting of all child-parent pairs of spanning
trees. Our algorithm implicitly traverses D from T 0 by recursively scanning all children
of a current spanning tree. Thus we must find all children of a given spanning tree, if they
exist. The next lemma gives a useful idea for this.
Lemma 3.2. [9] Let T p be an arbitrary spanning tree of G; and let f; g be two distinct
edges. Under assumptions (1), (2), and (3), T nf[g is a child of T p if and only if
f and g satisfy the following conditions:
Proof. Under assumptions (1) and (3), T c is a child of T p if and only if the following
conditions hold:
T c is a spanning tree different from T
ng
We first show that are
different spanning trees. Assume on the contrary that f 62 T
T c is a spanning tree and f 6= g; we have which is a
contradiction. Thus, f 2 T p and g 62 ng
must hold.
Conditions (3.2), (3.3), and (3.4) imply
On the other hand, under assumption (2), (3.1) implies (3.5). Moreover, (3.1) and (3.5)
imply (3.2) and (3.4). All we have to do is to show that (3.1) and (3.3) are equivalent under
conditions (3.2), (3.4), and (3.5).
From definition of T c and (3.5), T Hence
This implies that
only are distinct, g 2 Cyc(T c [f) is
equivalent to g 2 Cut(T p nf): Therefore, the second condition of (3.1) is equivalent to the
second condition of (3.3).
Let e k be the largest edge less than Min(T From this lemma, we can find all
children of T p if we know the edge-sets Cut(T p ne ne
Consider the graph defined in Figure 1 and T In this case, e 1 and e 2
are the only edges smaller than Min(T
Therefore, T 1 has only the two children T 1 ne 2 [e 4 and T 1 ne 1
In the rest of paper we shortly write Cut(T p ne ne
grounds that any edge in Cut(T p ne ne can be 'entered' into T p in place
of From the above consideration, we can construct the algorithm as below.
algorithm
input: a graph G with a vertex-set fv and an edge-set
begin
by using a depth-first search,
1 find a depth-first spanning tree T 0 of G,
vertices and edges to satisfy assumptions (2), (3), (4), and (5);
end .
procedure find-children(T p
input: a spanning tree T p and an integer k with e
begin
for each g 2 Entr(T do begin foutput all children of T p not containing e k g
ne k [g ;
ffind the children of T c g
ffind the children of T p not containing e k01 g
end .
In this algorithm, procedure find-children( ) finds all children of each spanning tree. When
it is called with two arguments T p and k; it finds all children of T p not containing
an edge finds such a child T c ; it recursively calls itself again for finding
all children of T c : In this stage, arguments are set to T c and k01; because if k ? 1
then e k01 becomes the largest edge less than Min(T all children of T p not

Figure

4: enumeration tree of spanning trees in G 1
containing e k have been found, it recursively calls itself again for finding all children of
T p not containing e k01 : In this case arguments are T p and k01: Initially, algorithm
all-spanning-trees(G) calls find-children( ) with arguments T 0 and V 01; and all spanning
trees of G are found. Figure 4 shows the enumeration tree of spanning trees in graph
Theorem 3.3. [9] Algorithm all-spanning-trees( ) outputs each spanning tree exactly once.
Proof. From Lemma 3.2, every spanning tree different from T 0 is output once for each
time its parent is output. From Lemma 3.1, for any spanning tree T c other than T
parent always exists and is uniquely determined. Since T 0 is the ancestor of all spanning
trees, the algorithm outputs each spanning tree exactly once.
Manipulating data structures.
In our algorithm, we define each state when we find all children of T p not containing e k
by a pair (T p ; k): When we call procedure find-children(T p ; k), the current state becomes
and if we find a child T c of T p not containing e k ; the state moves to (T c ; k01):
After all children of T p not containing e k have been found, the state moves to (T p ; k01):
At the state (T p ; k); the entering edge-set Entr(T is required to output all children
of T p not containing e k : After the state moves to (T c ; k01) (or (T p ; k01) ), the
necessity of the entering edge-set Entr(T c ; e k01 occurs for the first
time. The key point is finding an entering edge-set Entr(T c ; e k01
efficiently. For constructing an entering edge-set efficiently, our implementation maintains
edge-sets defined below. Let T p be a spanning tree and
:{
:{
e
e
e2e
:{
:{
e
e
e
e

Figure

5: movement of the state and Can(3; 3;
k be a positive integer with e For each edge e j (j
Here we use this notation in the sense that Can(e is a set of 'candidates' of
the entering edges leaving edge e j at the state (T p ; k): We can
find very easily by maintaining Can(e
definition (4.1). When we find a child T c of T p ; we
update On
the other hand, after we have found all children of T p not containing e k01 ; we construct
Efficiency of
our implementation depends on how to maintain Can(3; 3; efficiently.

Figure

5 shows states and edge-sets Can(3; 3; during enumerating all spanning trees
of G 1 in

Figure

1. For example, at the initial state (T 0 ; 3);
At the succeeding states
and
Here we consider how to maintain such edge-sets. First we show that the initial edge-sets
can be found easily.
Lemma 4.1. [9] Under assumptions (1), (2), (3), and (4),
Proof. Since ne can be written as:
ne
ne h
Under assumptions (1) and (4), an edge e 62 T 0 belongs to Cut(T 0 ne j ) if and only if @ 0 e
is a descendant of @ 0 e j and @ + e is an ancestor of @
only if @ 0 e  @ 0 e j and @ In addition, under assumption (3), for e 62
the largest edge with e 2 Cut(T 0 ne j ) if and only if @
From the lemma, we can find Can(e
applying a depth-first search.
Lemma 4.2. For any spanning tree T p and any positive integer k with e k !
be an arbitrary edge in Entr(T assumptions
(1), (2), (3), and (4), the following relation holds for a spanning tree ne k [g and an
where A is the set of ancestors of the edge e t in T 0 with @ 0 e
Proof. We note that if g 2 Entr(T is a child of T p , and that if
then
Each descendant of @ 0 e k relative to T p is a descendant of @ 0 g relative to T;
and vice versa. Therefore, for any e j 2 A; Entr(T; e
is an ancestor of e k then Entr(T; e j precisely, for any edge
such that @ 0 e is a descendant of @ 0 e k relative to T p ; e does not
belong to Entr(T; e j ); and the other edges obviously belong to Entr(T; e j That is
not an ancestor of e
Lemma 4.3. [9] Let T p be a spanning tree and let k be a positive integer with e k !
assumptions (1), (2), (3), and (4), for any edge g 2 Can(e
and for a spanning tree ne k [g; the following relation holds :
Proof. From the assumptions, for two edges e and f with
an ancestor of f relative to T 0 if and only if e is an ancestor of f relative to T p ; so
we will omit the phrase 'relative to T 0 (or T p )' for such edges. Let e t be the edge with
it exists, and let A be the set of edges in T 0 which are ancestors of e t if
We prove (4.4) by using the relation (4.3).
Case
Case
there is no edge e h with Therefore,
If e j is a proper ancestor of e t then Entr(T
Lemma 4.3 guarantees that at most one of sets Can(3; T updated when we want
to find all children of T c or all children of T p containing In Figure 5, when the state
moves from (T 0 ; is the edge such that @ 0 e and the following
equations hold:
On the other hand, when the state moves from (T 0 ; 3) to (T 1 ; 2); no candidate edge-set
is updated because there is no edge with @
In our implementation, we use global variables candi(3) and leave: At the state
represents the edge-set Can(e
variable leave represents the edge-set fe We can
check in constant time whether the current spanning tree has children or not by checking to
see if leave 6= ;: Suppose that each edge-set is represented as an ascending ordered list
realized by a doubly linked list. We also use a data structure for a given graph G so that
two incidence vertices of any edge are found in constant time, and a data structure for the
initial spanning tree T 0 so that for any vertex v other than the root, the unique edge e
with @ is found in constant time. Recall that graph G satisfies:
Assumption (5). For any two edges
From this assumption, one can find the edge-set Can(e searching
the ordered list candi(e k ) from the beginning. Thus we can complete this in time
proportional to the size of this edge-set. Merging two edge-sets can be executed in time
proportional to the sum of the size of two edge-sets. Therefore, it takes O(jCan(e
updating edge-sets candi(3) when the current
state goes to a succeeding state (T; k01): If candi(e t ) changes from empty to
nonempty then we must insert an edge e t into leave: Since leave is an ascending ordered
list, we can complete it in O(jfe2leaveje!e t
time.
On the other hand, when the state goes back from (T; k01) to (T p ; k); we must
reconstruct Can(3; T To do this, we must restore the edges
gg from candi(e t ) to candi(e k In the Shioura-Tamura algorithm
[9], such a restoration is efficiently executed by recording Can(e
before state (T p ; goes to (T; k01): This idea, however, requires O(V E) extra space
since the depth of recursive calls of the algorithm is O(V ). In the rest of this section, we
discuss our idea for reducing extra space.
denote the head-set of edges contained in Can(e
Lemma 4.4. Under assumptions (1), (2), (3) and (4), all head-sets Head(e
are mutually disjoint at any state (T p ; k):
Proof. From Lemma 4.1, Head(e at the initial state (T 0
nonempty. Thus the assertion is true at the initial state.
We assume that the lemma holds at the state (T p ; and prove that this holds at
the next state (T p ne k [g; k01); where From Lemma 4.3, the
following relation holds:
where HS is the head-set of all edges in Can(e
and each Head(e does not intersect HS, all
head-sets are mutually disjoint.
By Lemma 4.4, the head-set HS of edges in Can(g; T
with any head set Head(e Hence, if we can find HS before
restoring candi(3); it is easy to pick up the edges
In

Figure

5, when the state goes back from (T 0 ; 1) to (T 0 ; 2), all edges in Can(e
must be restored from candi(e 1 to
The head-set of Can(e is equal to fv 3 g: In this case,
reconstruct Can(e
Our implementation uses global variables head(3) for representing each Head(e
for k at state (T p ; k): Suppose that each head-set is represented by a (not
necessarily ascending) doubly linked list. From Lemma 4.4, we require O(V ) space for
manipulating these head-sets.
Now we describe two procedures for manipulating data structures candi(3); leave;
and head(3) when the current state (T p ; goes to a succeeding state (T; k01) or
goes back to (T p ; k); respectively. The procedure for the first case is shown
below:
procedure update-data-structure(e k ,g) ;
f the current state (T p ; goes to a succeeding state (T; ne k [g; k01) g
begin
e t := the edge in T 0 with @ 0 e
move
if candi(e t ) changes from empty to nonempty then insert e t into leave ;
HS := the head set of the edges in fe2candi(e k )j@
for each maximal sublist of consecutive elements of HS in head(e k ) do begin
record the first element of the sublist and its position in head(e k ) on a stack ;
delete the sublist from head(e k
add this to the end of head(e t
record the position of the first element of HS in head(e t ) on a stack ;
end .
When the state changes from (T p ; to (T; k01); we must move the head-set HS of all
edges in Can(e gg from head(e k ) to head(e t time, we do
not move each element of HS one by one, but move each maximal sublist of consecutive
elements of HS in head(e k ) to head(e t ) as Figure 6. Then extra space for recording
positions of such maximal sublists is O(V ) in all because the number of maximal sublists
is at most jhead(e k ) unchanged until the state comes
back to (T p ; k): It is easy to manipulate head(3) in the same time as candi(3);
because jHSj  jCan(e Here we omit details. Thus the time
maximal sublists
the first element
of maximal sublists
stack
v1 A

Figure

update of head(3)
complexity of the procedure is O(jCan(e
t and Can(e
The second procedure restores data structures in the following way:
procedure restore-data-structure(e k ,g) ;
f the state (T p ne k [g; k01) goes back to (T p ;
begin
e t := the edge in T 0 with @ 0 e
find HS by the record of the position of its first element in head(e t
delete HS from head(e t
move fe2candi(e t )j@ 0 e 2 HSg from candi(e t ) to the beginning of candi(e k
if candi(e t ) changes from nonempty to empty then delete e t from leave ;
move each sublist in HS to the correct place in head(e k ) by using records on a stack ;
end .
Since we recorded the first element of head vertices which were added to head(e t ); we can
find HS in constant time. For each edge in candi(e t ); we can check in constant time
whether it is in HS; by marking all elements of HS in advance. Hence we can restore
in O(jCan(e
time. Deletion of an edge from leave is completed in constant time. The head-set HS is
returned from head(e t ) to head(e k ) in time proportional to the number of maximal sublists
by the information of the places in head(e k Therefore, procedure restore-data-structure( )
takes O(jCan(e
5 An optimal implementation and its analysis.
Finally we describe our efficient implementation and analyze its time and space complex-
ities. Our implementation is written as below.
algorithm
input: a graph G with a vertex-set fv and an edge-set
begin
by using a depth-first search, (simultaneously) execute
1 find a depth-first spanning tree T 0 of G,
vertices and edges to satisfy assumptions (2), (3), (4) and (5),
1 for each e j
1 for each e j
end .
procedure find-children( :current spanning treeg
begin
e k := the last entry of leave;
delete e k from leave;
while do begin
:= the last entry of candi(e k
delete g from candi(e k ), and add g to the beginning of Q
ne k [gg
restore-data-structure(e
move all entries of Q to candi(e k
restore-data-structure(e k ,e k
add e k to the end of leave;
end .
Now we discuss the time complexity of our implementation. The next lemma is useful
for analyzing the time complexity.
Lemma 5.1. [9] Suppose that T is a spanning tree and that k is a positive integer
with assumptions (1), (2), (3), and (4), for any edge g j 2
is a spanning tree.
Proof. Let
a spanning tree. We suppose that T j is a spanning tree. If j  2; from Lemma 4.3,
ne j01 [g j01 is a spanning tree.
In algorithm all-spanning-tree( ), the time required other than calling find-children( ) is
O(V +E). At the state (T p ; k); O(# of children of T p not containing e k ) time is taken
to execute procedure find-children( ) other than maintenance of data structures. Now
we consider the time complexities of maintenance of data structures. From the discussion
in Section 4, it takes O(jCan(e
t and Can(e to maintain data structures when the state changes between
ne k [g; k01); where e t is an edge with @ We consider the next
two cases:
Case A: maintenance for finding children of T c (i.e., g 2 Can(e
Case B: maintenance for finding children of T p containing e k (i.e.,
Note that Case A occurs exactly one time for each spanning tree T c other than T 0 ; and that
Case B occurs at most one time for each spanning tree T p and for each edge e k 2 feje 1
In Case A,
by the number of children of T c not containing e t : Moreover, for each edge e j with
and Can(e there is a child of T c not containing e Therefore, the time
complexity in Case A is O(# of children of T c ). In Case B,
is bounded by the number of children of T p not containing e
has at least jfe2Can(e
neither e k nor e t : Similarly, jfe bounded by the
number of grandchildren of T p not containing e k : Thus the time complexity in Case B is
O(# of children of T p not containing e k ) +O(# of grandchildren of T p not containing e k
We recall that procedure find-children( ) checks in constant time whether T p has children.
From the above discussion, the total required time of find-children( ) at the state (T p ;
O(# of children and grandchildren of T p not containing e k )
Thus, the total time complexity of our implementation is O(N+V +E).
Finally we consider the space complexity. At any state, edge-sets candi(e j
have no intersection with each other, and neither do head-sets head(e j
Thus, we need O(V +E) space for candi and O(V ) space for head:
Obviously, the cardinality of leave is at most V 01. As we described in Section 4, the
size of the stack recording positions maximal sublists of HS is O(V ) in all. The total
size of local variables Q in find-children( ) is O(E) because each edge is stored in one
of global variables candi(3) or local variables Q: Hence, the space complexity of our
implementation is O(V +E).
Theorem 5.2. The time and space complexities of our implementation are O(N+V +E)
and O(V +E), respectively.
In this paper, we proposed an efficient algorithm for enumerating all spanning trees. This
is optimal in sense of time and space complexities.

Acknowledgements

We are greatly indebted to Dr. Yoshiko Ikebe of Tokyo Institute of Technology for her
kind and valuable comments on this manuscript.



--R

"A basis enumeration algorithm for linear systems with geometric applications,"
"A pivoting algorithm for convex hulls and vertex enumeration of arrangments and polyhedra,"
"Reverse search for enumeration,"
"Finding all spanning trees of directed and undirected graphs,"
"Algorithms for generating all spanning trees of undirected, directed and weighted graphs,"
"An algorithm for finding all the spanning trees in undirected graphs, "
"A Simple Algorithm for Listing All the Trees of a Graph,"
"Bounds on backtrack algorithms for listing cycles, paths, and spanning trees,"
"Efficiently scanning all spanning trees of an undirected graph,"
"Depth-first search and linear graph algorithms,"
--TR
spanning trees;undirected graphs;optimal algorithm