P446: Enumeration of all spanning trees in an undirected graph

P446: Enumeration of all spanning trees in an undirected graph

Input:

An undirected graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + N)$ total time with $O(|V||E|)$ space, where $N$ is the number of solutions.

Comment:

Constant amortized time.

Reference:

[Kapoor1995] (Bibtex)