4 ms·

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 he

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: http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s... 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: http://bl.ocks.org/mbostock/11159599 http://bl.ocks.org/mbostock/11159599

sltkr 12y ago
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.
- mbostock 12y ago
  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. [1] http://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim.27s_algorithm http://en.wikipedia.org/wiki/Maze_generation_algorithm#Rando...
  - sltkr 12y ago
    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).

sltkr 12y ago

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.

mbostock 12y ago
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. [1] http://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim.27s_algorithm http://en.wikipedia.org/wiki/Maze_generation_algorithm#Rando...
- sltkr 12y ago
  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).