Я всегда смешиваю, использую ли я стек или очередь для DFS или BFS. Может ли кто-нибудь объяснить некоторую интуицию о том, как запомнить, какой алгоритм использует структуру данных?
Нарисуйте небольшой график на листе бумаги и подумайте о порядке обработки узлов в каждой реализации. Как порядок, с которым вы сталкиваетесь с узлами и порядок, в котором вы обрабатываете узлы, различается между поисками?
Один из них использует стек (сначала по глубине), а другой использует очередь (в ширину) (для нерекурсивных реализаций, по крайней мере).
Очередь обычно может считаться горизонтальной в структуре, т.е. ширина/ширина может быть отнесена к ней - BFS, тогда как
Стек визуализируется как структура вертикальная и, следовательно, имеет глубину - DFS.
BFS сначала исследует/обрабатывает самые близкие вершины, а затем движется наружу от источника. Учитывая это, вы хотите использовать структуру данных, которая, когда queried дает вам самый старый элемент, на основе заказа, который они вставляли. Очередь - это то, что вам нужно в этом случае, поскольку она является первым в первом - выход (FIFO). В то время как DFS исследует, насколько это возможно, вдоль каждой ветки сначала, а затем - с помощью брекетов. Для этого стек работает лучше, поскольку это LIFO (последний раз в первый раз)
Я помню это, держа в голове барбекю. Барбекю начинается с буквы "B" и заканчивается звуком "q", поэтому BFS → Queue и оставшиеся DFS → стек.
Возьмите его в алфавитном порядке...
.... B (BFS)..... C...... D (DFS)....
.... Q (Очередь)... R...... S (Stack)...
BFS использует всегда очередь, Dfs использует структуру данных стека. Как показывает более раннее объяснение, DFS использует обратное отслеживание. Помните, что backtracking может выполняться только Stack.
BFS; = ширинa > очереди
Распределенная; Глубина = > стопка
Обратитесь к их структуре
Поиск по глубине использует Stack, чтобы запомнить, куда он должен идти, когда он достигает тупика.
DFSS
Стек (Last In First Out, LIFO). Для DFS мы извлекаем его из корня в самый дальний node как можно больше, это та же идея, что и LIFO.
Очередь (First In First Out, FIFO). Для BFS мы получаем один уровень на один уровень, после того как мы посетим верхний уровень node, мы посещаем нижний уровень node, это та же идея, что и FIFO.
Вы можете вспомнить, сделав аббревиатуру
BQDS
Прекрасная Королева совершила грехи.
На хинди, ब हुरानी क्यु द र्द स हा
Я хотел бы поделиться этим ответом: fooobar.com/questions/340895/...
Взяв BFS и заменив очередь на стек, воспроизводит тот же порядок посещения DFS, он использует больше места, чем фактический алгоритм DFS.
Более простой способ запоминания, особенно для молодых студентов, заключается в использовании аналогичной аббревиатуры:
BFS => Boy FriendS в очереди (для популярных дам по-видимому).
В противном случае DFS (стек).
Ничего не помню
Предполагая, что структура данных, используемая для поиска, равна X:
Breadth First= Узлы, введенные ранее X, должны сначала генерироваться на дереве: X - это очередь.
Depth First= Узлы, введенные X позже, должны сначала быть сгенерированы на дереве: X - стек.
Вкратце: стек - это последний в очереди, то есть DFS. Очередь "первым пришел - первым обслужен", то есть BFS.