A new algorithm for generating all arborescences ∑r+ of a given directed graph G = （V

E）

with vertex r∈V as root

is suggested. It gives as the result an expression of a form of so-called "direct products-direct sums"

which is especially suitable for the practical applications of the original problems from which the topical generation of all arborescences was abstracted.The new algorithm （GEN） is based upon two sorts of graph decomposition namely

the decomposition of a graph G = （V∪{r}. E） into several "sub-configurations" （a new concept）G[Vt] = （V1

E（V1））

∪1=V

V1∩V1=φ

E（V1）= ∪VEV1 E-v

giving direct products:vev

∪（G）= x∑G[V1])

and the decomposition of the in-arc set of a vertex

E-v = D1∪D2

D1∩D2 =φ

giving direct sums: ∑（G） = ∑（G1）∪∑（G2）

∑（G1）∑（G2） =φ.A new concept

（proper） back-arc

is formulated

and an algorithm （DEL） for deleting such arcs is proposed. The deletion of such arcs has not any effect on the set ∑r+.The complexity of the above algorithms is as follows: for the algorithm DEL

the time is O（EV）

the space is O（E）; for the algorithm GEN

the time is O （EVK）

the space is O（E）

where V and E are the cardinal of the vertex set

and the cardinal of the arc set （of the given graph G） respectively

and K is the times of call for algorithm DEL by algorithm GEN

i. e. the number of the appearances of the sign " + ’’ （the sign of direct sum） in the resulted expression.