1
$\begingroup$

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. 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.
Queue contents: [(1, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (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.
Queue contents: [(2, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
Marking (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(3, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (3, 3)
Goal reached at (3, 3)
$\endgroup$
  • $\begingroup$ If you can get from position A to position B and vice versa, you're starting at A, and neither of them is the goal, it seems that your implementation will enter an infinite loop. $\endgroup$ – Yuval Filmus Sep 24 '18 at 15:01
1
$\begingroup$

Yes. There is no point having duplicates in the queue, so don't enqueue a position if (a) it has already been visited, or (b) it is already on the queue.

What happens if you skip checking whether it is already on the queue? Depending on how the rest of your code works, this could slow down your implementation significantly (it could increase the asymptotic running time from linear to quadratic).

$\endgroup$
  • $\begingroup$ Thanks, that's helpful. I'm wondering though, will the duplicates always be next to each other so that I can just check if the tail matches the new element? It seems that searching through the whole queue kind of defeats the point of the data structure, maybe? $\endgroup$ – Robin Sep 24 '18 at 16:57
  • $\begingroup$ @Robin, nope, not necessarily. Don't search through the whole queue. Instead, store them in a hashtable, or use a bit in the object for the vertex (the same way you'd keep track of which nodes have been visited). $\endgroup$ – D.W. Sep 24 '18 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.