Talk:Maze generation algorithm

The Kruskal's algorithm as stated is/was slow and unnecessarily restrictive! Kruskal's algorithm works on any connected graph, not just rectangular and hexagonal matrices. Kruskal's algorithm does usually take O (E log E) because finding the least costly edge each time costs (log E). In the random Kruskal's algorithm you just need to select a random edge each time, which only costs O(1). So the cost will be number of edges times the cost to join two regions. But it is easy to show that there are disjoint set implementations that can perform the needed union-find operations in constant time, so the total time to generate the maze is only O(E). This actually goes for the depth first search as well. Kevin Saff 04:21, 7 Feb 2004 (UTC)