Duplicate elements in Queue for BFS Maze Algorithm
I'm fairly new to studying data structures and algorithms.
I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and 0s (spaces), marking visited positions with 3.
However, I notice that there are duplicate values in the Queue. 923
I understand that I should avoid visiting already visited positions. However the queue contains only "prospective" positions which are yet to be visited. Should I modify the algorithm to not enqueue positions which it already contains? Will the algorithm still work if I do so?
As far as I know I have implemented the following algorithm:
Create a queue for positions yet to explore, and enqueue the entrance (0,0)
While the list is not empty
dequeue
If it is the goal position,
exit displaying position and success message
Otherwise,
mark the position as visited, and enqueue all valid neighbors (not walls and not visited)
If the list is empty and the method has not returned, there is no path
Some sample output is below:
Enqueueing (0,0)
Queue contents: [(0, 0)]
Press Enter to continue:
Dequeueing
Current position: (0, 0)
Marking (0, 0)
[3, 1, 1, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 1)]
Press Enter to continue:
Dequeueing
Current position: (0, 1)
Marking (0, 1)
[3, 1, 1, 0]
[3, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 1), (0, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 1)
Marking (1, 1)
[3, 1, 1, 0]
[3, 3, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 2), (2, 1), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (0, 2)
Marking (0, 2)
[3, 1, 1, 0]
[3, 3, 0, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 1), (1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (2, 1)
Marking (2, 1)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
Marking (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 3), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 3)
Marking (1, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 0, 2]
Enqueueing coordinates of valid positions in 4 directions. 180