Я всегда смешиваю, использую ли я стек или очередь для DFS или BFS. Может ли кто-нибудь объяснить некоторую интуицию о том, как запомнить, какой алгоритм использует структуру данных?Как я могу запомнить, какие структуры данных используются DFS и BFS?
Нарисуйте небольшой график на листе бумаги и подумайте о порядке обработки узлов в каждой реализации. Как порядок, с которым вы сталкиваетесь с узлами, и порядок, в котором вы обрабатываете узлы, различаются между поисками?
Один из них использует стек (по глубине), а другой использует очередь (в ширину) (для нерекурсивных реализаций, по крайней мере).
BFS сначала исследует/обрабатывает самые близкие вершины, а затем движется наружу от источника. Учитывая это, вы хотите использовать структуру данных, которая, когда queried дает вам самый старый элемент, на основе заказа, который они вставляли. Очередь - это то, что вам нужно в этом случае, поскольку она является первым в первом - выход (FIFO). Принимая во внимание, что DFS исследует, насколько это возможно, вдоль каждой ветви, а затем - брекеты. Для этого стек работает лучше, так как он LIFO (последний раз в первый раз)
BFS использует всегда очередь, DFS использует структуру данных стека. Как показывает более раннее объяснение, DFS использует обратное отслеживание. Помните, что backtracking может выполняться только Stack.
BFS; Ширина => очередь
Распределенные; Глубина => стопка
Обратитесь к их структуре
Я помню, держа барбекю в моем сознании. Барбекю начинается с буквы «B» и заканчивается звуком «q», поэтому BFS -> Queue и оставшиеся DFS -> стек.
Очередь может быть принято считать, как горизонтальной в структуре т.е. широты/ширина можно отнести к ней - BFS, тогда как
Стек визуализируется как вертикальной структуры и, следовательно, имеет глубина - DFS.
Красивая визуальная подсказка для новых учеников. +1. – displayName
Поиск по глубине использует Stack, чтобы запомнить, куда он должен идти, когда он достигнет тупика.
DFSS
Возьмите его в алфавитном порядке ...
.... B (BFS) ..... С ...... D (ДФС). ...
.... Q (Queue) ... R ...... S (Stack) ...
Я хотел бы поделиться этот ответ: https://stackoverflow.com/a/20429574/3221630
Принимая BFS и заменяя очередь стеком, воспроизводит тот же порядок посещения DFS, он использует больше места, чем фактический алгоритм DFS.
Стек (Last In First Out, LIFO). Для DFS мы извлекаем его из корня в самый удаленный узел как можно больше, это та же идея, что и LIFO.
Очередь (First In First Out, FIFO). Для BFS мы получаем один уровень на один уровень, после того как мы посещаем верхний уровень узла, мы посещаем нижний уровень узла, это та же идея, что и FIFO.
Хорошее наблюдение :) – RBT