Как я могу вспомнить, какие структуры данных используются DFS и BFS?

Question

Я всегда смешиваю, использую ли я стек или очередь для DFS или BFS. Может ли кто -нибудь предоставить некоторую интуицию о том, как помнить, какой алгоритм использует какую структуру данных?

Answer 1

Нарисуйте небольшой график на листе бумаги и подумайте о порядке, в котором узлы обрабатываются в каждой реализации. Как порядок, в котором вы сталкиваетесь с узлами, и порядок, в котором вы обрабатываете узлы между поисками?

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

Answer 2

Очередь в целом можно рассматривать как горизонтальный в структуре т.е. ширина/ширина может быть приписан этому - BFS, тогда как

Куча визуализируется как вертикальный структура и, следовательно, имеет глубина - DFS.

Answer 3

BFS сначала исследует/обрабатывает ближайшие вершины, а затем выходит наружу от источника. Учитывая это, вы хотите использовать структуру данных, которая при запросе дает вам самый старый элемент, основанный на порядок, который был вставлен. Очередь-это то, что вам нужно в этом случае, так как она впервые в первую очередь (FIFO). Принимая во внимание, что DFS исследует как можно дальше вдоль каждой ветви сначала, а затем BrackTracks. Для этого стек работает лучше, так как это LIFO (последнее в первую очередь)

Answer 4

Я помню это, сохраняя барбекю в моей голове. Барбекю начинается с «B» и заканчивается звуком, подобным «Q» отсюда BFS -> очереди и оставшимся DFS -> стеком.

Answer 5

Возьмите это в алфавитном порядке ...

.... B (BFS) ..... C ...... D (DFS) ....

.... Q (очередь) ... R ...... S (стек) ...

Answer 6

BFS использует всегда в очереди, DFS использует структуру данных стека. Как более раннее объяснение рассказывает о DFS, использует обратную связь. Помните, что обратная связь может продолжаться только по стеку.

Answer 7

BFS; ширина => очередь

Dfs; debin => стек

Обратитесь к их структуре

Answer 8

В поисках глубины используется Stack вспомнить, куда он должен идти, когда он достигнет тупика.

DFSS

Answer 9

1. Стек (последний в первом выходе, Lifo). Для DFS мы извлекаем его из Root в самый дальний узел, насколько это возможно, это та же идея, что и LIFO.

2. Очередь (сначала в первую очередь, FIFO). Для BFS мы забираем его на один уровень на одну далелю, после того, как посещаем верхний уровень узла, мы посещаем нижний уровень узла, это та же идея, что и FIFO.

Answer 10

Более простой способ запомнить, особенно для молодых студентов, - использовать аналогичную аббревиатуру:

BFS => Friends в очереди (по -видимому, для популярных женщин).

DFS - это иначе (стек).

Answer 11

Ничего не помни.

Предполагая, что структура данных, используемая для поиска Икс:

Широта сначала = Узлы введены Икс Ранее сначала нужно генерировать на дереве: X - очередь.

Глубина первой = Узлы введены Икс Позже сначала сгенерировать на дереве: X - это стек.

Короче говоря: стек последнего в первую очередь, что является DFS. Очередь сначала в первую очередь, что является BFS.

Answer 12

Я хотел бы поделиться этим ответом:https://stackoverflow.com/a/20429574/3221630

Принимая BFS и заменив очередь стеком, воспроизводит тот же порядок посещения DFS, он использует больше места, чем фактический алгоритм DFS.

Answer 13

Вы можете вспомнить, сделав аббревиатуру

Bqds

Красивая королева сделала грехи.

На хинди,बहुरानी क्यु दर्द सहा