queue - キューを使用せずに幅優先検索または幅優先トラバーサルは可能ですか?

Question

私が覚えてチェックしたように、ツリーをトラバースしたり、Web 幅優先 (BFS) をクロールしたりする通常の方法は、キューを使用することです。実際にキューを使用せずに実装する方法はありますか?

Answer 1

この質問はもう古いことは知っていますが、答えたかっただけです。これは、配列、リンクされたリスト (またはその他の線形コンテナー) を使用して、再帰なしで行うことができます。oldとの 2 つのコンテナーを保持し、 のすべてのアイテムをトラバースするとき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

実装が簡単なため、実際にはキューを使用する必要があります。また、キューを使用すると、複数のマシンを連携させることができます (1 つのマシンがサイトをキューに登録し、別のマシンがキューからサイトをポップしてトラバースします)。

これを行う唯一の他の方法は、再帰を使用することです (はるかに難しく、メモリの使用量はわずかに増減するだけです)。

Answer 3

再帰あり。しかし、キューはスタックにあります...