Применение. Обход дерева в глубину

Применение

Самый первый пример применения графов - это социальная сеть. Вершинами графа являются люди, а ребрами отношения (дружба). Граф может быть неориентированным, то есть я могу дружить только с теми кто дружит со мной. Либо ориентированным (как например в ЖЖ), где можно добавить человека в друзья, без того чтобы он добавлял вас. Если же он да добавит вас вы будете «взаимными друзьями». То есть будет существовать два ребра: (Он, Вы) и (Вы, Он)
Ещё одно из применений графа, которое я уже упоминал это ссылки с сайта на сайт. Представим Вы хотите сделать поисковую систему и хотите учесть на какие сайты есть больше ссылок (например сайт A), при этом учитывать сколько сайтов ссылается на сайт B, который ссылается на сайт A. У вас будет матрица смежности этих ссылок. Вы захотите ввести какую то систему подсчёта рейтинга, которая делает какие то подсчёты на этой матрице, ну, а дальше… это Google (точнее PageRank) =)

Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.

Обходы деревьев нужны собственно для того чтоб оптимально быстрой найти необходимый элемент в дереве. Собственно обход дерева, как и все обходы графов ( а дерево это обычный неориентированный граф ) делается двумя методами: в глубину (Depth-first) и в ширину (Breadth-first).

Обход дерева в глубину

Обход в глубину производится рекурсивно либо с использованием стека. В обоих случаях можно обходить узлы дерева в различной последовательности. Обход начинается от корня. Выделяют три наиболее важных порядка обхода в глубину:

префиксный (прямой) обход — сначала обрабатывается текущий узел, затем левое и правое поддеревья;
инфиксный (симметричный) обход — сначала обрабатывается левое поддерево текущего узла, затем корень, затем правое поддерево;
постфиксный (обратный) обход — сначала обрабатываются левое и правое поддеревья текущего узла, затем сам узел.

В качестве примера рассмотрим следующее дерево:

· префиксный обход: A, B, D, H, E, C, F, I, J, G

· инфиксный обход: D, H, B, E, A, I, F, J, C, G

· постфиксный обход: H, D, E, B, I, J, F, G, C, A

Задание 1. У Маши есть 2 конверта: обычный и экспресс, и 3 марки: круглая, прямоугольная и треугольная. Сколькими способами Маша может выбрать конверт и марку, чтобы отправить письмо?

Задание 2. На дополнительное занятие по физической культуре пришли восемь учащихся: Саша, Маша, Таня, Артём, Женя, Лёша, Настя и Юра. Физкультурный руководитель Николай Владимирович попросил их построиться по росту. Известно, что Саша выше Маши, Таня выше Артёма, Женя ниже Лёши, но выше Насти, Настя выше Саши, Лёша ниже Юры, а Маша выше Тани. Давайте поможем ребятам выстроиться по росту.

Задание 3: Сколько трёхзначных чисел можно составить из четырёх цифр: 1, 2, 3 и 4.

⇐ Предыдущая 1 234 Следующая ⇒