11
2
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 & 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.
See my answer; are complex number coordinates to distinguish vertices allowed? – Value Ink – 2019-12-30T08:00:40.077
@ValueInk Yes, it's allowed. – Bubbler – 2019-12-30T08:12:52.850
1
As the challenge stands now, I could generate graphs randomly, check if the current graph is a spanning tree, else repeat. The program will have random running time (usually very large), but will finish with probability 1. You may want to rule that out (not sure how). Or is that acceptable?
– Luis Mendo – 2019-12-30T13:21:28.7871@LuisMendo I was about to go write an algorithm doing exactly like that to make a point... BogoSpanningTree – FlipTack – 2019-12-30T17:38:31.203
The randomness part of the challenge seems needlessly tacked on to a perfectly fine challenge. – Post Rock Garf Hunter – 2019-12-31T00:41:47.090
Is it acceptable for my ASCII grid to bordered by whitespace on all sides? – Neil – 2019-12-31T01:06:54.833
@Neil Yes, it's fine. – Bubbler – 2019-12-31T05:14:05.863
1@LuisMendo I have no problem with such a solution (though the challenge was indeed inspired from the "minimum random spanning tree" Wikipedia article). – Bubbler – 2019-12-31T05:25:49.830