3. Алгоритмы построения минимального остовного дерева (мод)

   1. Общие сведения о задаче построения мод

Действия алгоритмов построения минимального остовного дерева T

	0	11	9	7	8
	11	0	15	14	13
R 	9	15	0	12	14
	7	14	12	0	6
	8	13	14	6	0	,

рассмотрим на конкретных примерах матрицы расстояний R. Пусть задана симметричная матрица расстояний R:

которой можно поставить в соответствие взвешенную полносвязную сеть G с

n=5 вершинами и m=10 ребрами, представленную на рис. 5.

1

8 11

13

5 2

^G 7 9

₆ 14 14

15

₄ 12 ₃

Рис. 5. Исходная сеть G для построения МОД

Тогда минимальным остовным деревом T сети G является самая дешевая подсеть, т.е. подсеть минимального веса, которая покрывает все вершины сети G и не содержит циклов. Очевидно, что такая подсеть является деревом.

Для построения минимального остовного дерева T во взвешенной, связной и полной сети G с n вершинами и m ребрами можно использовать ряд алгоритмов, среди которых наиболее известными являются алгоритмы Крускала и Прима.

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

Данный алгоритм содержит следующие основные шаги:

Шаг 0. [Инициализация] Создаем сеть T с n вершинами, но без ребер.

Создаем сеть H идентичную сети G.

Шаг 1. [Цикл] До тех пор, пока сеть T не является связной сетью выполнять шаг 2, в противном случае STOP.

Шаг 2. [Отыскание ребра с наименьшим весом] Пусть (u,v) – ребро с наименьшим весом в сети H. Если при добавлении ребра (u,v) к сети T в последней не образуется циклов, то это ребро добавляется к T.

Шаг 3. [Удаление (u,v) из H] Удаляем ребро (u,v) из сети H.

На рис. 6 представлен пример построения с помощью алгоритма

Крускала минимального остовного дерева T для исходной сети G, изображенной на рис. 5.

1

₈ 11

4

¹ 13

5

⁷ 2 ^{3 9}

Образуется ¹

цикл

8

4

11

₂ 5 ₂

7 ₂

H T _{1 9} ³

_{6 1} ¹⁴ 14 ⁶

15

₄ ¹² 3 ^{4 3}

Рис.6. Пример построения минимального остовного дерева по алгоритму Крускала

Порядок присоединения ребер (u,v) к сети T и удаления этих ребер из сети H указан цифрами в квадратах на соответствующих ребрах этих сетей. Из рис. 6 видно, что на третьем этапе претендентом на присоединение к T является ребро (5,1), как имеющее на данном этапе в сети H наименьший вес 8. Однако его присоединение к T не происходит, так как оно приводит к появлению цикла (1,4,5,1), и на третьем этапе присоединяется следующее по значению ребро (1,3) с весом 9.

Необходимость решения вопросов о связности сети и наличии в ней циклов делают алгоритм Крускала недостаточно эффективным. Следующий алгоритм, разработанный Примом, гарантирует построение минимального остовного дерева без проведения проверок создаваемой сети на связность и наличие в ней циклов.