是否可以在不使用队列的情况下进行广度优先搜索或广度优先遍历？

Question

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

Answer 1

我知道这个问题现在已经很老了，但我只是想回答一下。您可以使用数组、链表（或任何其他线性容器）来完成此操作，而无需递归。保留两个容器，old和new，并在遍历 中的所有项目时old交换。与队列的实现非常相似。newold

在 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

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

我认为做到这一点的唯一其他方法是使用递归（更加困难，并且仅使用少量或多或少的内存）。