Почему алгоритм BFS использует очередь?

Question

Я смотрю на псевдокоде в Википедии

Breadth-First-Search(Graph, root): 
2 
3  for each node n in Graph:    
4   n.distance = INFINITY   
5   n.parent = NIL 
6 
7  create empty queue Q  
8 
9  root.distance = 0 
10  Q.enqueue(root)      
11 
12  while Q is not empty:   
13  
14   current = Q.dequeue() 
15  
16   for each node n that is adjacent to current: 
17    if n.distance == INFINITY: 
18     n.distance = current.distance + 1 
19     n.parent = current 
20     Q.enqueue(n) 

https://en.wikipedia.org/wiki/Breadth-first_search

и что мне любопытно, о том, есть ли конкретная причина, почему queueu используется для хранения узлов. Мне кажется, что можно использовать любой контейнер, так как порядок прохождения элементов, находящихся в контейнере, не имеет значения.

Answer 1

Очередь - это не только контейнер. Это ключевая идея для этого алгоритма.

Очередь 1. контейнер для проверки. 2. Это может быть только добавление/поп определенной последовательностью (в очереди и стеке есть оба атрибута)

Второй момент - это ключевой момент для ответа на ваш вопрос.

Если вы используете очередь в качестве общего списка, добавьте и поместите элемент непосредственно через индекс списка, весь алгоритм не может быть таким простым. (то есть очередь больше не является очередью)