queue - 不使用队列是否可以进行广度优先搜索或广度优先遍历？

Question

我记得并检查过，遍历树或首先爬取网络广度 (BFS) 的常用方法是使用队列。实际上有没有一种方法可以不使用队列来实现它？

Answer 1

我知道这个问题现在很老了，但我只是想回答。您可以使用数组、链表（或任何其他线性容器）来执行此操作，而无需递归。保留两个容器，old和new，并old在new遍历old. 与队列的实现非常相似。

在 Python 中，它看起来像：

def breadth_first(root):
    if not root:
        return
    old = []
    new = []
    old.append(root)
    while old:
        for n in old:
            process(n)  # Do something
            if n.left:
                new.append(n.left)
            if n.right:
                new.append(n.right)
        old = new
        new = []

运行时复杂度与队列实现相同，O(n)。

Answer 2

你真的应该使用队列，因为它更容易实现。此外，队列允许多台机器一起工作（一个队列站点，而另一个从队列中弹出站点以进行遍历）。

我看到的唯一另一种方法是使用递归（要困难得多，并且只使用或多或少的内存）。

Answer 3

带递归。但是队列在堆栈中......

Answer 4

如果您关心订购，请使用队列。queue 保留插入顺序。或者您可以使用列表的实现，例如两个数组列表来交替。但从根本上说，list 也保留了排序。

如果您不关心排序，则可以使用任何集合实现。sets 不保留此顺序。

例如，在 BFS 实现中，如果你不关心节点的顺序，你可以使用两个集合，旧的和新的来交替，而不是一个队列。