6.8.2. Алгоритм ближайшего соседа построения остовного дерева

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

1. Построение остовного дерева начинается с произвольной вершины

2. Затем среди ребер, инцидентных х выбираем ребро с наименьшим весом и включаем его в дерево

3. Повторяя процесс, выполняем поиск наименьшего по весу ребра, соединяющего вершины с некоторой другой вершиной графа

4. Процесс включения ребер продолжаем до тех пор, пока все вершины исходного графа не будут включены в дерево Построенное дерево будет минимальным остовным. Доказательство того, что последовательность шагов 1—4 приводит к построению минимального остовного дерева, аналогично доказательству для жадного алгоритма. Реализация схемы ближайшего соседа формирования остовного дерева выполнена в алгоритме 6.9, где исходный граф представляется матрицей весов веса несуществующих ребер полагаются равными Под весами ребер понимаются их длины. Остовное дерево формируется посредством реберного списка и списка вершин В качестве меток вершин устанавливаются их порядковые номера Для каждой вершины еще не включенной в остовное дерево, поддерживается минимальное расстояние до множества ранее включенных вершин в Это осуществляется с помощью двух векторов где равно минимальному расстоянию от вершины Обновление значений векторов выполняется на каждом шаге алгоритма при пополнении новой вершиной.

• Сложность алгоритма ближайшего соседа. Сложность алгоритма определяется двумя вложенными циклами по числу вершин. В каждом из циклов выполняется константное число операций. Следовательно, сложность составляет

Алгоритм 6.9. Алгоритм ближайшего соседа для остовного дерева

(см. скан)

(см. скан)

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

Алгоритм 6.10. Программа алгоритма ближайшего соседа

(см. скан)

(см. скан)

(см. скан)

(см. скан)

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

• в первой строке содержится количество вершин в графе;

• в следующих строках задаются верхние диагональные элементы (нулевые диагональные элементы включаются) строк матрицы весов.

Результаты расчетов сохраняются в выходном файле со следующей структурой:

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