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

Алгоритм Крускала

Читайте также:
  1. RSVP алгоритммен тарату жүйесіне QoS-көрсеткішінің табу әдістемесі
  2. Алгоритм
  3. Алгоритм 1. Сила Мистического Сознания.
  4. Алгоритм 2. Состояние ДИВО (Динамической Воли).
  5. Алгоритм 3. Состояние Имагинатора.
  6. Алгоритм 4. Кристаллизация Я.
  7. Алгоритм введения и изменения заряда точки привязки

Другой алгоритм построения МОД предложил Крускал. Алгоритм начинает работу с пустого дерева. К нему добавляются ребра в порядке возрастания их весов до тех пор, пока не будет получен набор ребер, объединяющий все вершины графа. В процессе выполнения необходимо не допускать добавление ребер, приводящих к появлению цикла в создаваемом дереве. Если ребра закончатся до того, как все вершины будут соединены между собой, это означает, что граф был несвязным, и полученный результат представляет собой объединение МОД всех его компонент связности. Пример алгоритма приведен ниже:

1. Отсортировать ребра в порядке возрастания весов

2. Инициализировать структуру разбиений

edgeCount=l

while edgeCount<=E and includedCount<=N-l do

parentl=FindRoot(edge[edgeCount].start)

parent2=FindRoot(edge[edgeCount].end)

if parentl/=parent2 then

добавить edge[edgeCount] в остовное дерево

includedCount=includedCount+l

Union(parent1,parent2)

end if

edgeCount=edgeCount+l

end while

 

Для иллюстрации действия алгоритма будем использовать граф, приведенный на Рис. 3.6.

Рис. 3.11. Добавление первого ребра

Рис. 3.12. Добавление второго и третьего ребра

Рис. 3.13. Добавление четвертого и пятого ребер

Рис. 3.14. Заключительные шаги алгоритма Крускала


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


<== предыдущая страница | следующая страница ==>
Алгоритм Дейкстры-Прима| Алгоритм Дейкстры

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