As far as I know, Breadth-First-Search [BFS] theory traditionally requires a Queue to process a given level of a graph (i.e: wiki seems to assume so).
- A Queue is a Collection
- A Set is also a Collection, for example
Wiki states that BFS...
"explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level."
What about that quote requires specifically a Queue? Why would BFS not work if implemented with any other type of Collection besides a Queue?
It seems to me that as long as any Collection is used to explore "all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level", by storing such neighbor nodes in that Collection and ensuring the entire Collection is emptied (or otherwise completely processed or explored) before moving on to the next depth level, then the level-ordering requirement of BFS is achieved?
I understand that a Queue would ensure a certain order (i.e: left-to-right) while processing/exploring within a given level; but is that ordering within a given level really necessary such that the algorithm still meet the requirements of BFS? Otherwise why is order within a given level actually necessary?