2.5 Построение остовного дерева

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

Прежде всего, необходимо представлять, какие данные, в какой форме используются при работе алгоритмов.

В алгоритме используются следующие данные.

Множество исследуемых вершин (множество И) – по данному множеству массиву контролируются уже просмотренные вершины.

Основная цепь (ОЦ) - одномерный массив. Заполняется в процессе работы алгоритма. В исходном состоянии пуст (содержит нули).

Матрица векторов смежности (МВС) - двумерный массив, строки соответствуют элементам ОЦ. Каждая строка является вектором смежности для вершины, занесенной в соответствующую строку ОЦ.

Результирующая цепь (РЦ) - одномерный массив, в него заносится последовательность вершин, образующих искомую цепь, но в обратном порядке, от N1 до N2.

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

В процессе выполнения обратного хода по векторам смежности последовательно прослеживается, начиная от конечной вершины N2, цепь дуг, связывающая её с начальной вершиной N1.

Используемое в обоих алгоритмах понятие “очередная просматриваемая вершина” означает вершину, для которой в настоящее время ищутся смежные.

По алгоритму поиска “в глубину” сначала строится путь на максимальную глубину, то есть пока есть дуги, продолжающие путь, затем производится ветвление от конечной вершины.

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

Исходные данные: множество дуг, N1 - начальная вершина цепи, N2 - конечная вершина цепи.

Прямой ход.

Этап 0. Все вершины заносятся в множество И (исследуемые вершины).

1. Начальная вершина N1 заносится в основную цепь (ОЦ), в качестве очередной просматриваемой (ОП) принимается первая вершина из ОЦ.

2. Вершина ОП вычеркивается из И.

3. Выявляется очередная вершина из множества И, смежная с ОП (ВСОП).

4. Если ВСОП нет, то ОП вычеркивается из ОЦ. В качестве ОП принимается предшествующая вершина из ОЦ. Переход к П.2.

5. Если ВСОП не является искомой вершиной N2, то ВСОП помещается очередным элементом в вектор смежности вершины ОП и в основную цепь (ОЦ). Иначе - переход к П.7.

6. В качестве ОП принимается следующая вершина из ОЦ. Переход к П.2.

7. Конец прямого хода.

Обратный ход.

Обратный ход начинается от найденной вершины N2.

0. Принять в качестве вершины, заносимой в результирующую цепь (вершины ЗЦ), вершину N2.

1. Занести вершину ЗЦ в результирующую цепь. Если вершина ЗЦ является вершиной N1, то перейти к П5.

2. Выявить вершину из основной цепи (вершину О), в вектор смежности которой входит вершина ЗЦ.

3. Найти вершину О среди вершин, входящих в векторы смежности.

4. Принять вершину О в качестве вершины ЗЦ. Перейти к Э.1.

5. Переписать результирующую цепь наоборот.

6. Конец алгоритма.

Пример выполнения прямого хода алгоритма поиска “В глубину” приведен в прил. 1.

При поиске в ширину в первую очередь производится просмотр всех вершин, смежных с очередной просматриваемой, только затем поиск смещается ниже, то есть в качестве очередной просматриваемой берется первая из ранее выявленных смежных вершин.

Алгоритм поиска "в ширину".

Исходные данные: множество дуг, N1 - начальная вершина цепи, N2 - конечная вершина цепи.

Прямой ход.

0. Все вершины заносятся в множество И (исследуемые вершины).

1. В качестве очередной просматриваемой (ОП) вершины берется начальная вершина N1. Вершина ОП заносится в основную цепь.

2. Вершина ОП заносится в основную цепь. Вершина ОП вычеркивается из И.

3. Выявляются все вершины множества И, смежные с ОП (ВВСОП). ВВСОП вычеркиваются из И и заносятся в вектор смежности вершины ОП.

4. Если среди ВВСОП нет N2, то ВВСОП заносятся в ОЦ, в качестве ОП берется очередная вершина из ОЦ, переход к П.3; иначе - конец прямого хода.

Обратный ход.

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