Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритм Прима определение минимального остовного дерева(случай многоуровнего графа)

Читайте также:
  1. II.Проанализировать сегодняшнее положение организации с точки зрения достижения главной цели → определение слабых и сильных сторон.
  2. IV. Новый материал. Определение выпуклых и невыпуклых многоугольников. №284
  3. Quot;Алгоритм глупости"?
  4. XI. ОПРЕДЕЛЕНИЕ ПОБЕДИТЕЛЕЙ И ПРИЗЕРОВ
  5. А) ВЕРБАЛЬНОСТЬ КАК ОПРЕДЕЛЕНИЕ ГЕРМЕНЕВТИЧЕСКОГО ПРЕДМЕТА
  6. А. ОПРЕДЕЛЕНИЕ
  7. А. ОПРЕДЕЛЕНИЕ

 

По заданному графу заполняется матрица весов W(N,N). Веса несуществующих ребер предполагаются сколь угодно большими. Образуется массив P(N) меток вершин графа (столбцов матрицы весов). Алгоритм решения задачи заключается в последовательном заполнении массива меток столбцов и состоит из следующих этапов.

Предварительный этап. Обнуляется массив P(N) меток столбцов таблицы. Произвольно выбранному столбцу присваивается значение метки, равное его номеру.

Общий этап. В строках, номера которых равны номерам помеченных столбцов, находится минимальный элемент среди элементов непомеченных столбцов. Столбец, в котором находится минимальный элемент, помечается меткой, номер которой равен номеру его строки, а элементу с ”транспонированными” индексами присваивают значение ∞ (он симметричен относительно главной диагонали).

Заключительный этап. Ребра дерева определяются по меткам столбцов, вес дерева определяется суммой весов ребер.

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

0 Таблица 5

i                 tp
                   
                   
                   
                   
                   
                   
                   
                   
tп                  

 

Задачей общего этапа является помечивание всех столбцов таблицы. В 0-й строке находится минимальный элемент w01=70. 1-й столбец, содержащий минимальный элемент, помечается номером строки, где этот элемент находится, т.е. номером 0. Элементу w10 присваивается сколь угодно большое значение.

Затем в непомеченных столбцах 1-й строки находится минимальный элемент w12=120, тогда 2-й столбец помечается номером 1, а элементу w21 присваивается значение ∞.

Во 2-й строке минимальный элемент w23=60, 3-й столбец, содержащий w23=60, помечается номером 2, w32=∞.

В 3-й строке w34=40, 4-й столбец помечается номером 3, а элемент w43=∞.

В 4-й строке w45=20, 5-й столбец помечается номером 4, а элемент w54=∞.

В 5-й строке w56=30, 6-й столбец помечается номером 5, а элемент w65=∞.

В 6-й строке w67=15, 7-й столбец помечается номером 6, а элемент w76=∞.

Т.к. в 7-й строке все элементы равны бесконечности, то на этом общий этап закончен. В результате таблица примет вид, представленный в табл. 6.

Таблица 6

0 0 1 2 3 4 5 6

i                 tp
                   
                 
                 
                 
                 
                 
                 
                 
tп                  

 

На заключительном этапе выписывается последовательность вершин, ребра между которыми включаются в минимальное остовное дерево. Это ребра, соединяющие вершины 0-1, 1-2, 2-3, 3-4, 4-5, 5-6, 6-7. Вес остовного дерева равен 70+120+60+40+20+30+15=355. Полученное остовное дерево имеет вид:

 

x2 x4 x6

x0

 

 

70 120 60 40 20 30 15

 

x1 x3 x5 x7

 


Дата добавления: 2015-08-21; просмотров: 173 | Нарушение авторских прав


Читайте в этой же книге: Принятие решения о работоспособности объекта | Получение уравнения гиперплоскости, проходящей через n заданных точек. | Сетевой график | Решение задачи о кратчайшем пути в графе на основе ЛП | Минимизация булевых функций в классе КНФ (Конъюнктивная нормальная форма). | Конечный автомат | Алгоритм венгерского метода | Решение задачи коммивояжера | Алгоритм метода ветвей и границ |
<== предыдущая страница | следующая страница ==>
Алгоритм построения всех остовных деревьев графа на основе полного перебора последовательности ребер или дуг| Расчет сетевого графа на основе линейного программирования

mybiblioteka.su - 2015-2024 год. (0.008 сек.)