That code does NOT implement Prim's algorithm on a graph with randomly-weighted edges. Instead it just does a randomized breadth-first search of the area (starting from the corner), which is the same algorithm used for colouring, which is why the radial pattern occurs.
For a randomized spanning tree, edges should be generated with a random weight, and Prim's algorithm extracts them from the frontier ordered by weight. This creates a very different tree structure that is much more similar to the uniform spanning tree generated by Wilson's algorithm.
I’d be happy if you could explain more, but the edges here are intentionally unweighted, so I believe the algorithm is correct. It’s based on the description here:
EDIT: Looks like you’re right! It makes a huge difference if you assign each edge a random weight once, rather than simply pulling a random edge of the frontier. Seems like the reference I used has this bug? Here is a fixed version:
Yeah, I'm pretty sure the site you linked is wrong too, and I think the author doesn't realize it, because he says:
> My last post was about using Kruskal’s algorithm to generate random mazes. This article is about using another minimal spanning tree algorithm to do the same: Prim’s algorithm.
But his implementation is NOT the same! (His implementation of Kruskal's algorithm does look correct.) Extracting elements at a random index is not equivalent to assigning random weights to elements and extracting the minimum-weight elements.
I spoke to Jamis Buck on Twitter. It’s called “Randomized Prim’s” on Wikipedia [1], but of course Wikipedia is not authoritative. It does seem confusing to call it a variant of Prim’s given how different the behavior is.
I see -- apparently it's common to call this "Prim's algorithm" even though it is more accurately described as a randomized variant of breadth/depth-first search. Thanks for clarifying that.
I do still object to the text reading "This article is about using another minimal spanning tree algorithm to do the same" -- what is described there is not a minimal spanning tree algorithm (even if it's called Prim's algorithm).
For a randomized spanning tree, edges should be generated with a random weight, and Prim's algorithm extracts them from the frontier ordered by weight. This creates a very different tree structure that is much more similar to the uniform spanning tree generated by Wilson's algorithm.
(This comment is based on the code from this page: http://bl.ocks.org/mbostock/11159599)