Эйлеров обход: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) (Новая страница: «=Идея= Эйлеров обход -- способ представить подвешенное неориентированное дерево массиво...») |
Глеб (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | = | + | ==Определение== |
Эйлеров обход -- способ представить подвешенное неориентированное дерево массивом чисел. Существуют несколько способов построить такой обход и каждый вариант обход имеет свои плюсы и минусы. | Эйлеров обход -- способ представить подвешенное неориентированное дерево массивом чисел. Существуют несколько способов построить такой обход и каждый вариант обход имеет свои плюсы и минусы. | ||
| − | =Варианты= | + | ==Варианты== |
1) Давайте выпишем все рёбра дерева (ориентированные) в порядке DFS'а. Именно такой подход описан на википедии | 1) Давайте выпишем все рёбра дерева (ориентированные) в порядке DFS'а. Именно такой подход описан на википедии | ||
Текущая версия на 10:06, 27 ноября 2019
Определение
Эйлеров обход -- способ представить подвешенное неориентированное дерево массивом чисел. Существуют несколько способов построить такой обход и каждый вариант обход имеет свои плюсы и минусы.
Варианты
1) Давайте выпишем все рёбра дерева (ориентированные) в порядке DFS'а. Именно такой подход описан на википедии
2) Каждая вершина добавляется в массив дважды: когда мы в неё заходим и когда выходим(то есть когда ставим tin, tout). Каждому листу соответствует два последовательных вхождения(кроме может быть одной вершины, подумайте какой).
3) Каждая вершина добавляется в массив всякий раз, когда мы её посещаем (когда спускаемся из предка и поднимаемся из потомка).
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin