При обходе дерева / графика в чем разница между шириной первой и глубиной первой? Любые примеры кодирования или псевдокода были бы хороши.
172
При обходе дерева / графика в чем разница между шириной первой и глубиной первой? Любые примеры кодирования или псевдокода были бы хороши.
Ответы:
Эти два термина различают два разных способа ходьбы по дереву.
Вероятно, проще всего показать разницу. Рассмотрим дерево:
Глубины первого обхода будет посещать узлы в таком порядке
Обратите внимание, что вы продвигаетесь вниз на одну ногу, прежде чем двигаться дальше.
Ширину первого обхода будет посетить узел в этом порядке
Здесь мы работаем до конца каждый уровень , прежде чем вниз.
(Обратите внимание, что в приказах прохождения есть некоторая двусмысленность, и я обманул, чтобы поддерживать порядок «чтения» на каждом уровне дерева. В любом случае я мог добраться до B до или после C, и аналогично я мог бы получить до E до или после F. Это может иметь или не иметь значение, зависит от вашей заявки ...)
Оба вида обхода могут быть достигнуты с помощью псевдокода:
Разница между двумя порядками прохождения заключается в выборе
Container
.Рекурсивная реализация выглядит так
Рекурсия заканчивается, когда вы достигаете узла, у которого нет дочерних элементов, поэтому он гарантированно завершится для конечных ациклических графов.
На данный момент я все еще немного обманул. С небольшим умом вы также можете работать с узлами в следующем порядке:
это изменение глубины в первую очередь, когда я не выполняю работу на каждом узле, пока не иду обратно по дереву. Однако я посетил более высокие узлы на пути вниз, чтобы найти их детей.
Этот обход является вполне естественным в рекурсивной реализации (используйте строку «Альтернативное время» выше вместо первой строки «Работа»), и не слишком сложный, если вы используете явный стек, но я оставлю это в качестве упражнения.
источник
A, B, D, C, E, F
- первый представленный), инфикс (D, B, A, E, C, F
- используемый для сортировки: добавить как дерево AVL, затем прочитать инфикс) или постфикс (D, B, E, F, C, A
альтернативный вариант). Имена задаются позицией, в которой вы обрабатываете корень. Следует отметить, что инфикс действительно имеет смысл только для двоичных деревьев. @batbrat это имена ... учитывая время, прошедшее с тех пор, как ты спросил, ты, наверное, уже знаешь.Понимание условий:
Эта картинка должна дать вам представление о контексте, в котором используются слова широта и глубина .
Поиск в глубину:
Алгоритм поиска в глубину действует так, как если бы он хотел как можно быстрее отойти от начальной точки.
Обычно он использует,
Stack
чтобы запомнить, куда он должен идти, когда он заходит в тупик.Соблюдайте следующие правила: толкните первую вершину A на
Stack
Java-код:
Приложения : Поиск в глубину часто используется при моделировании игр (и игровых ситуаций в реальном мире). В типичной игре вы можете выбрать одно из нескольких возможных действий. Каждый выбор ведет к дальнейшему выбору, каждый из которых ведет к дальнейшему выбору, и так далее, в постоянно расширяющийся древовидный график возможностей.
Поиск в ширину:
Queue
.Java-код:
Приложения : Поиск в ширину сначала находит все вершины, которые находятся на расстоянии одного ребра от начальной точки, затем все вершины, которые находятся на расстоянии двух ребер, и так далее. Это полезно, если вы пытаетесь найти кратчайший путь от начальной вершины до данной вершины.
Надеюсь, этого будет достаточно для понимания поисков по ширине и глубине. Для дальнейшего чтения я бы порекомендовал главу «Графики» из превосходной книги Роберта Лафора о структурах данных.
источник
Учитывая это двоичное дерево:
Ширина первого обхода:
проход через каждый уровень слева направо.
«Я G, мои дети D и я, мои внуки B, E, H и K, их внуки A, C, F»
Глубина первого обхода:
обход не выполняется по всем уровням одновременно. Вместо этого обход вначале погружается в ГЛУБИНУ (от корня до листа) дерева. Тем не менее, это немного сложнее, чем просто вверх и вниз.
Есть три метода:
Использование (иначе, почему мы заботимся):
Мне очень понравилось это простое объяснение Quora методов глубинного обхода и того, как они обычно используются:
«Обход по порядку будет печатать значения [для BST (дерево двоичного поиска)] "
„Предварительный заказ обход используется для создания копии [бинарного дерева поиска].“
Msgstr "Обратный путь по порядку используется для удаления [бинарного дерева поиска]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing
источник
Я думаю, что было бы интересно написать их так, чтобы только переключение некоторых строк кода дало вам один или другой алгоритм, так что вы увидите, что ваша дилемма не так сильна, как кажется на первый взгляд. ,
Мне лично нравится интерпретация BFS как затопление ландшафта: сначала будут затоплены районы с низкой высотой, и только затем последуют районы с большой высотой. Если вы представляете высоты ландшафта как изолинии, как мы видим в книгах по географии, легко увидеть, что BFS заполняет все области одной и той же изолинии одновременно, как это было бы с физикой. Таким образом, интерпретация высоты как расстояния или масштабированной стоимости дает довольно интуитивное представление об алгоритме.
Имея это в виду, вы можете легко адаптировать идею, лежащую в основе поиска в ширину, чтобы легко найти минимальное связующее дерево, кратчайший путь, а также многие другие алгоритмы минимизации.
Я еще не видел какой-либо интуитивной интерпретации DFS (только стандартная для лабиринта, но она не такая мощная, как BFS и флуд), поэтому мне кажется, что BFS лучше соотносится с физическими явлениями, как описано выше, в то время как DFS лучше коррелирует с выбором дилеммы в рациональных системах (т.е. люди или компьютеры решают, что делать в шахматной игре или выходить из лабиринта).
Таким образом, для меня разница между ложью, на которой природные явления лучше всего соответствуют их модели распространения (трансверсинга) в реальной жизни.
источник