Find all spanning trees of a directed weighted graph

Question

I have found this paper so far. Is it outdated? Are there any faster and better implementations?

By the way, Wikipedia says that there can be n^n-2 spanning trees in a undirected graph. How many spanning trees can be in a directed graph?

Answer 1

If you use terms from paper you mentioned and you define spanning tree of directed graph as tree rooted in vertex r, having unique path from r to any other vertex then:

It's obvious that worst case when directed graph has the greatest number of the spanning trees is complete graph (there are a->b and b->a edges for any pair). If we "forget" about directions we will get n^{n-2} spanning trees as in case of undirected graphs. For any of this spanning trees we have n options to choose a root, and this choice define uniquely define directions of edges we need to use. Not hard to see, that all trees we get are spanning, unique and there are no nother options. So we get n^{n-1} spanning trees. Strict proof will take time, I hope that simple explanation is enough.

So this task will take exponential time depend from vertex count in worst case. Considering the size of output (all spanning trees), I conclude that for arbitrary graph, algorithm can not be significantly faster and better. I think you need to somehow reformulate your original problem to not deal with all spanning trees, and may be search only needed by some criteria.

Answer 2

for undirected graph only....

n^n-2 spanning tress are possible for only complete graph....to find total number of spanning trees of any graph u can apply this method.....

1. find the adjacency matrix of the graph.
2. if column values are represented by 'i' and row entries by 'j' then...
3. if i=j...then the value will be the degree of vertex
4. suppose,there is a single edge between vertex v1 and v2 then the value of matrix entry will be -1......7 if there are two edges then it will be -2...& so on...
5. after constructing adjacency matrix....exclude any row and column...i.e, Nth row and Nth column....
6. answer will be the total number of spanning tress.