P74: Enumeration of all spanning tree in an weighted graph

P74: Enumeration of all spanning tree in an weighted graph

Input:

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

Output:

All spanning tree of $G$ in increasing order of weight.

Complexity:

$O(N\log |V|+|V||E|)$ total time and $O(N + |V|^2|E|)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Kapoor1991] (Bibtex)