возможен ли поиск в ширину или в обход в ширину без использования очереди?

Question

Как я помню и проверил, обычный способ обхода дерева или обхода ширины веб-страниц (BFS) - использование очереди. Есть ли способ реализовать это, не используя очередь?

Answer 1

Я знаю, что этот вопрос сейчас старый, но я просто хотел ответить. Вы можете сделать это с массивами, связанными списками (или любым другим линейным контейнером) и без рекурсии. Оставьте два контейнера old и new и поменяйте местами old с new, когда вы пройдете через все элементы в old. Очень похоже на реализацию с очередью.

В Python это будет выглядеть так:

<code>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

Вы действительно должны использовать очередь, так как ее легче реализовать. Кроме того, очередь позволяет нескольким машинам работать вместе (один сайт очередей, а другой выталкивает сайты из очереди для прохождения).

Единственный другой способ сделать это - использовать рекурсию (гораздо сложнее и использует лишь незначительно больше или меньше памяти).

Answer 3

, если вы заботитесь о заказе, используйте очередь. Очередь сохраняет порядок вставки. или вы можете использовать реализацию списка, скажем, два списка массивов, чтобы чередовать. Но, по сути, список также сохраняет порядок.

если вы не заботитесь о порядке, вы можете использовать любые реализации набора. наборы не сохраняют этот порядок.

Например, в реализации BFS, если вы не заботитесь о порядке узлов, вы можете использовать два набора: старый и новый для чередования, а не очередь.

Answer 4

с рекурсией. Но очередь в стеке ...