宽度优先搜索或宽度优先遍历是否可以不使用队列?

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

我看到的唯一的另一种方法是使用递归(更困难,并且只使用很少的内存)。

我知道这个问题已经老了,但我只是想回答。您可以使用数组、链接列表(或任何其他线性容器)进行此操作,而无需递归。保留两个容器, 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)相同。

使用递归。但队列在堆栈中…

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

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

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