![](/user_photo/2706_HbeT2.jpg)
Алгоритм
1.
На множестве вершин (выводов) M(i)
построить взвешенный полный граф (число
ребер в нем n(n-1)/2
). Для этого
вычислить элементы матрицы расстояний
по одной из формул:
или (5.1)
,
(5.2)
где
и
– координатыi-й
и j-й
позиций монтажного пространства.
Формулой (5.1) пользуются для монтажа «внавал», а формулой (5.2) – при жгутовом монтаже.
2.
Всем элементам, лежащим на главной
диагонали и ниже её, присваивается
значение
.
Присвоить нулевое значение длинеL
рёбер искомого дерева: L
= 0; i
= 0; j
= 0.
3.
Сформировать таблицу меток и локальных
степеней вершин:
;
;
;
;
.
4.
Присвоить
.
5.
Найти минимальный элемент
матрицы
.
6.
Если
,
то идти к 4.
7.
Если
или
,
то идти к 4.
8.
Поглощение меток: все метки нового
фрагмента получают значение
,
а локальные степени соединенных вершин
–
и
.
9.
Включить ребро
во множествоR
ребер минимального дерева, а длину
дерева увеличить на длину ребра:
.
10.
Если
,
то идти к 4, в противном случае к 11.
11. Минимальное дерево построено. R – множество его ребер, а L – суммарная их длина.
Конец.
Алгоритм Прима
Алгоритм Прима реализует следующую процедуру [1 – 7].
На каждом шаге просматриваются только те ребра графа, которые связы-вают вершины строящегося поддерева с новыми, еще не присоединенными вершинами, т.е. ищется вершина, ближайшая от всего построенного фрагмента дерева. Отсюда, в отличие от алгоритма Краскала, единственное строящееся поддерево последовательно наращивается до построения остова.
Основные
принципы построения минимального
связывающего дерева (или кратчайшей
связывающей сети) при наличии ограничений
на локальные степени вершин
следующие.
В
начале любая произвольная вершина
соединяется с ближайшей соседней,
образуя исходное поддерево. (Для
определенности построения мини-мального
дерева можно начинать с ребра, инцидентного
первой вершине
,
или с минимального ребра). На каждом
последующем шаге к строящемуся поддереву
присоединяют очередное ребро минимально
возможной длины, связывающее новую, еще
не присоединенную вершину
с одной из вершин поддеревьев
,
локальная степень которой
.
Для
реализации алгоритма составляют матрицу
расстояний
,
элемент
которой вычисляют по одной из формул
(5.1) или (5.2). Просматривают элементы
первой строки матрицыD
и находят минимальный элемент. Пусть
таким оказался элемент g-го
столбца, тогда весь 1-й и g-й
столбцы матрицы D
исключаются из рассмотрения, а первое
соединение проводится между точками
и
.
Просматриваются 1-я иg-я
строки матрицы с оставшимися элементами.
Из элементов этих строк находится
минимальный. Предположим, что им оказался
элемент, принадлежащий j-му
столбцу. Если этот элемент находится
на пересечении с первой строкой, то
точку
соединяем с 1-й точкой (
),
если же он находится на пересечении сg-й
строкой, то точку
соединяем сg-й
(
),
после чего из матрицыD
исключаем все элементы j-го
столбца. Просматриваются 1-я, g-я и j-я
строки и т. д.
Выполнение
ограничения на локальную степень
вершин обеспе-чивается проверкой в
каждой просматриваемойi-ой
строке числа уже выбранных для построения
минимального дерева элементов –
.
При
все оставшиеся элементыi-й
строки исключаются из рассмотрения,
т.е. эта строка удаляется.
АЛГОРИТМ
1.
Вычислить элементы матрицы расстояний
по одной из формул – (5.1) или (5.2).
2.
Найти минимальный элемент матрицы
,
где
;
.
Номера строки и столбцаq
и p,
на пересечении которых он находится,
определяют номера вершин
и
,
соединяемых ребром.
3.
Занести номера вершин во множество
,
построенное ребро – во множество
.
4.
Подсчитать локальные степени
и
,
подлежащих соединению на данном шаге
вершин
и
.
5.
Проверить условие
и
.
Индексы вершин, для которых это условие
не выполняется, указывают номера строк
матрицыD,
которые необходимо исключить из
рассмотрения.
6.
Найти
.
Здесь
,
,
т. е. среди еще не вошедших в дерево
вершин отыскать вершину
,
минимально удаленную от некоторой
вершины дерева
.
7.
Дополнить множества
;
.
8.
Проверить, все ли вершины графа соединены
ветвями
.
Если условие выполняется, идти к 9, иначе
– к 4.
Конец.