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

Question

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

Answer 1

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

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

Answer 2

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

Answer 3

Я помню это, храня в уме Барбекю.Барбекю начинается с буквы «B» и заканчивается звуком «q», поэтому BFS -> Queue и остальные DFS -> stack.

Answer 4

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

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

Answer 5

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

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

.... Q (Очередь) ... R ...... S (Стек) ...

Answer 6

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

Answer 7

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

DFSS

Answer 8

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

Распределенная; глубина => стек

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

Answer 9

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

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

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

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

Вкратце: стек является последним вFirst-Out, который является DFS.Очередь «первым пришел - первым обслужена», то есть BFS.

Answer 10

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

BFS => Boy FriendS в очереди (очевидно, для популярных девушек).

В противном случае DFS (стек).