The Wikipedia animation for Maze generation using DFS isn't consistent wrt the written algorithm given there, isn't it?

Question

Please have a look at this link:

http://en.wikipedia.org/wiki/Maze_generation#Depth-first_search

Here, the theoretical algorithm given is:

Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell.

But I don't think the animation on it's right uses the same algorithm to generate the maze, though it's not incorrect.

I feel the animation uses this algorithm:

1. Start with any unvisited cell, make it a part of the maze and mark it visited.
2. Add the unvisited neighbours of that cell to the set of cells that can be considered next
3. Choose any one of cells from the set and mark it visited.
4. Check if that cell does not have any neighbours that are visited except ONE (the one which caused this cell to be added to the set in the first place). Else go to 3.
5. Continue till all cells are visited.

Am I wrong?

Answer 1

The animation uses the algorithm that the article describes. Their stack consists of the cells that have been visited. When they reach a dead end, they backtrack by popping cells off the stack until they come across one that has an unvisited neighbor and then start exploring a path beginning at that cell (by pushing that cell onto the stack).

They are not keeping a set of unvisited cells and randomly choosing another one to visit. If you look closely, they always choose to explore starting at a cell closest to the red square.

If we label the cells so that the bottom left cell is (1, 1) and the top right cell is (30, 20) you notice that its first 'decision' at time 0:03 when it hits a dead-end at (1, 5). It backtracks to the last cell with an unvisited neighbor (1, 7) and is forced to explore (1, 8) next. If I understand the algorithm you describe, you would be randomly choosing a any cell which touched part of the path that was generated already.