Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

Question

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.

We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking out one row and column, and then taking the determinant of that sub-matrix.

Let's call that determinant t (i.e. there are t possible spanning trees in total).

What is the quickest known algorithm such that its input is G and it's output is one of t possible spanning trees of G (where each spanning tree has as close to $\frac{1}{t}$ chance of being selected as possible)?

Here's the algorithm I'm using currently.

---

Definitions:

$V_{visited}$ - vertices already traversed

$E_{visited}$ - edges already traversed

$V_C$ - V \ V_visited (i.e. vertices in V but not in $V_{visited}$)

N($V_{visited}$) - the set of all vertices v in $V_C$ such that an edge exists between v and some vertex in $V_{visited}$

---

Algorithm:

• sample $v_0$ from V randomly
• add $v_0$ to $V_{visited}$
• sample $v_1$ from N($V_{visited}$) randomly
• add ($v_0$, $v_1$) to $E_{visited}$
• sample $v_2$ from N($V_{visited}$) randomly
• add ($v_*$, $v_2$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_2$'s neighbors in $V_{visited}$)

...

• sample $v_{|V| - 1}$ (the second to last vertex in V) randomly
• add ($v_*$, $v_{|V| - 1}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V| - 1}$'s neighbors in $V_{visited}$)
• sample $v_{|V|}$ (the last vertex in V)
• add (v*, $v_{|V|}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V|}$'s neighbors in $V_{visited}$)

Now $V_{visited}$ and $E_{visited}$ represents a random spanning tree of G.

---

Is this the most efficient way of getting a random spanning tree? Is there a more efficient way? (Bonus points if it's parallelizable.)