P115: Enumeration of all spanning trees in a directed graph
P115: Enumeration of all spanning trees in a directed graph
Input:
A directed graph $G = (V, E)$.
Output:
All spanning trees in $G$.
Complexity:
$O(|E|+ND(|V|, |E|))$ total time and $O(|E|+DS(|V|, |E|))$ space.
Comment:
$D(|V|, |E|)$ and $DS(|V|, |E|)$ are the time and space complexities of the data structure for updating the minimum spanning tree in an undirected graph with $|V|$ vertices and $|E|$ edges. Here $N$ denotes the number of directed spanning trees in $G$.