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

As I remember and checked, the usual way for traversing a tree or crawling the web breadth first (BFS) is by using a queue. Is there actually a way to implement it not using a queue?

正如我记得并检查的那样,遍历树或首先爬网(BFS)的常用方法是使用队列。实际上有没有办法实现它不使用队列?

4 个解决方案

#1

You really should be using a queue, as its easier to implement. Also, a queue allows for multiple machines to work together (one queues site while another pops sites off of the queue to traverse).

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

The only other way I see to do this is by using recursion (much more difficult, and uses only marginally either more or less memory).

我认为这样做的唯一另一种方法是使用递归(更加困难,并且只使用或多或少的内存)。

#2

I know this question is old now, but I just wanted to answer. You can do this with arrays, linked lists (or any other linear container) and without recursion. Keep two containers, old and new, and swap old with new when you traverse all of the items in old. Very similar to the implementation with queue.

我知道这个问题现在已经过时了,但我只想回答。您可以使用数组,链接列表(或任何其他线性容器)执行此操作,而无需递归。当你遍历旧的所有物品时,保留两个旧的和新的容器,并用旧换新旧容器。非常类似于队列的实现。

In Python it would look like:

在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 = []

Runtime complexity would be the same as the queue implementation, O(n).

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

#3

With recursion. But the queue is in the stack...

随着递归。但队列在堆栈中......

#4

if you care about ordering, use queue. queue preserves the insertion ordering. or you can use list's implementation, say, two array lists, to alternate. But fundamentally, list preserves ordering too.

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

if you don't care about ordering, you can use any set implementations. sets doesn't preserve this ordering.

如果您不关心订购,您可以使用任何设置实现。集合不保留此顺序。

For example, in BFS implementation, if you don't care the ordering of nodes, you can use two sets, old and new to alternate, rather than a queue.

例如,在BFS实现中,如果您不关心节点的排序,则可以使用两个集合,旧的和新的交替,而不是队列。

#1