Ориентированные деревья

Алгоритм поиска в глубину

Поиск в глубину

Выбираем произвольную вершину V₀; выбираем смежную с ней V₁. Итак,

1. пусть граф задан матрицей смежности,

2. создадим одномерный массив В, количество элементов в котором совпадает с количеством вершин в графе. На каждом месте этого массива будем хранить номер вершины, в которую попали на этом шаге,

3. из всех смежных не пройденных вершин будем выбирать вершину с меньшим номером,

4. чтобы хранить список вершин, откуда еще есть куда отправиться, создадим еще один одномерный массив St[1..n].

Пусть задан граф G=(V,R), где V – множество вершин графа, R – множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. из множества всех белых вершин выберем любую, обозначим ее V₀;

2. найдем для нее все не пройденные смежные вершины и повторим поиск для них;

3. перекрашиваем ее в черный цвет;

4. повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Проще говоря: начиная с некоторого номера вершины V₀ идем «в глубь», пока это возможно. Процесс повторяется с вершиной V₁. Если на очередном шаге оказалось, что нет непросмотренных вершин, связанных с текущей, то выполняется возврат к предыдущей вершине и ищется новая вершина, связанная с ней. Если такой вершины не найдено, то выполняется еще один шаг возврата к предыдущей вершине, и так до тех пор, пока вычислительный процесс не вернется к вершине, с которой начат просмотр.

14 апреля

СРС: Придумать программу, в которой будут произведены различные действия над бинарными деревьями.

Корневое дерево – ориентированное дерево, в котором можно выделить вершины трех видов:

- корень,

- нетерминальные вершины,

- терминальные вершины (т.е. листья).

Пример:

РОТ

УШИ

ГЛАЗА

ТУЛОВИЩЕ

ГОЛОВА

ЖИВОТНОЕ

корень

нетерминальные вершины

терминальные

… … вершины

Структура корневого дерева:

1. в корень не входит ни одна дуга;

2. во все нетерминальные вершины входит только одна дуга;

3. из листьев не выходит ни одна дуга.

Бинарное дерево – корневое дерево, каждая вершина которого имеет не более двух потомков.

Следовательно, текущая вершина V имеет:

- предка,

- левого и правого потомка.

Высота дерева – максимальное количество дуг, между корнем и самым удаленным листом.

Высота дерева равна 2.

Дата добавления: 2014-01-20