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

Question

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

queueweb-crawlerbreadth-first-search

5

据我所记和检查，遍历树或广度优先搜索（BFS）爬行Web的常规方法是使用队列。实际上是否有一种不使用队列实现的方法？

- nonopolarity

不使用队列的目的是什么？ - AlbertoPL

只是为了知道实现它的不同方法。 - nonopolarity

也许我的评论已经过时了，但确实有一种方法可以做到这一点。https://dev59.com/fnE85IYBdhLWcg3w6oB0#2549825 - Herrington Darkholme

4个回答

2

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

我看到的另一种方法是使用递归（更加困难，使用的内存略微多一些或少一些）。

- AlbertoPL

如何使用栈来模拟队列？ - nonopolarity

可以使用两个栈。请参见https://dev59.com/oHVD5IYBdhLWcg3wKYL-。 - AlbertoPL

你展示的链接实现了一个使用两个栈的队列。但是如何将这个想法转换为BFS的递归实现呢？ - max

0

使用递归。但队列在栈中...

- eKek0

有没有一个简单的伪代码可以使用递归实现BFS？ - nonopolarity

1

我也很好奇。你想如何通过使用调用栈来高效地替换队列？ - Lucero

-1

如果您关心顺序，请使用队列。队列保留插入顺序。或者，您可以使用列表的实现，例如两个数组列表进行交替。但是基本上，列表也保留顺序。

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

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

- e230217

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mea · Accepted Answer

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

在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）。