BFS算法为什么要用队列？
Why does the BFS algorithm use a queue?
我在看维基百科上的伪代码
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 来保存节点是否有特定原因。在我看来，可以使用任何容器，因为遍历容器中当前元素的顺序是无关紧要的。
队列根本不仅仅是一个容器。这正是该算法的关键思想。
队列是
1.肯定是一个容器。
2、一定顺序只能add/pop（队列和栈都有这个属性）
第二点是回答你问题的重点
如果你把队列当做普通列表使用，直接通过列表索引添加和弹出元素，整个算法就没那么简单了。 （即队列不再是队列）
- 因为事先不知道frontier的大小，所以使用queue更节省内存。
- 队列数据结构被认为天生“公平”。作为队列基础的 FIFO 概念将确保首先探索那些最先发现的东西。
我在看维基百科上的伪代码
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 来保存节点是否有特定原因。在我看来，可以使用任何容器，因为遍历容器中当前元素的顺序是无关紧要的。
队列根本不仅仅是一个容器。这正是该算法的关键思想。
队列是 1.肯定是一个容器。 2、一定顺序只能add/pop（队列和栈都有这个属性）
第二点是回答你问题的重点
如果你把队列当做普通列表使用，直接通过列表索引添加和弹出元素，整个算法就没那么简单了。 （即队列不再是队列）
- 因为事先不知道frontier的大小，所以使用queue更节省内存。
- 队列数据结构被认为天生“公平”。作为队列基础的 FIFO 概念将确保首先探索那些最先发现的东西。