Random spanning tree of a rectangular grid Significantly harder version of Spanning tree of a rectangular grid.

Background

A spanning tree (Wikipedia) of an undirected graph is a subgraph that is a tree which includes all of the vertices of the original graph. The following is an example of a spanning tree of a 4-by-4 grid graph.



Task

Given two positive integers w and h, output a randomly generated spanning tree of the grid graph which has w vertices horizontally and h vertices vertically. Your program/function should be able to generate every possible spanning tree with nonzero probability.

One possible algorithm to solve this task is random minimum spanning tree, which calculates the minimum spanning tree of the given graph with randomized edge weights.

Input and output

The input is two positive integers w and h.

The output is a representation of a spanning tree. You can choose any representation that can describe such a graph without ambiguity, which includes (but is not limited to):


ASCII-formatted grid
A standard graph structure, e.g. adjacency matrix, adjacency list, incidence matrix...
A list of pairs of numbered vertices


Please specify the output format in your submission.

Scoring &amp; winning criterion

The standard code-golf rules apply. The shortest valid submission in bytes wins.

Example I/O

w=3, h=2


ASCII grid


+-+-+
| |
+ +-+



Adjacency matrix


0 1 0 1 0 0
1 0 1 0 1 0
0 1 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 1 0



List-of-vertex-pairs representation


[(0, 1), (0, 3), (1, 2), (1, 4), (4, 5)]


or

[((0, 0), (0, 1)),
 ((0, 0), (1, 0)),
 ((0, 1), (0, 2)),
 ((0, 1), (1, 1)),
 ((1, 1), (1, 2))]


w=1, h=1

The graph is a single vertex with no edges, and its only spanning tree is the graph itself.
Wolfram Language (Mathematica), 146 bytes

Block[{c,g=GridGraph@{##}},Graph[Range[1##],Join@@Reap[Do[c@n/._c:&gt;#0[Sow[#&lt;-&gt;n];n],{n,RandomSample@AdjacencyList[g,c@#=#]}]&amp;@1][[2]],Options@g]]&amp;


Try it online!

Based on my answer to the question Maze Generation.

Returns a Graph object.

For example, w = 20, h = 20 gives: