Эйлеров обход

Материал из Algocode wiki
Версия от 10:06, 27 ноября 2019; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение

Эйлеров обход -- способ представить подвешенное неориентированное дерево массивом чисел. Существуют несколько способов построить такой обход и каждый вариант обход имеет свои плюсы и минусы.

Варианты

1) Давайте выпишем все рёбра дерева (ориентированные) в порядке DFS'а. Именно такой подход описан на википедии

2) Каждая вершина добавляется в массив дважды: когда мы в неё заходим и когда выходим(то есть когда ставим tin, tout). Каждому листу соответствует два последовательных вхождения(кроме может быть одной вершины, подумайте какой).

3) Каждая вершина добавляется в массив всякий раз, когда мы её посещаем (когда спускаемся из предка и поднимаемся из потомка).



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin