7: do u ← EXTRACT-MIN(Ω)

8: foreach (для каждой) вершины v ∈Adj(u )

9: do if v ∈Ωиw (u , v ) < key[v ] then

10: p[v ] ← u

11: key[v ] ← w (u , v )

На рисунках 1–8 показана схема работы алгоритма Прима с корнем r.

Рисунок 1 – Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер

Рисунок 2 – Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.

Рисунок 3 – Следующее безопасное ребро с весом 11. Добавляем его

Рис. 4

Рисунок 5

Рисунок 6

Рисунок 7

Рисунок 8 – Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Время работы алгоритма Прима зависит от того, как реализована очередь с приоритетами Ω. Если использовать двоичную кучу, инициализацию в строках 1–4 можно выполнить за время O(V ). Далее цикл выполняется |V | раз, и каждая операция EXTRACT-MIN занимает время O(V logV ). Цикл for в строках 8–11 выполняется в общей сложности O(E ), поскольку сумма степеней вершин графа равна 2|E |. Проверку принадлежности в строке 9 можно выполнить за время O(1), если хранить состояние очереди еще и как битовый вектор размера |V |. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (DECREASE-KEY), которая для двоичной кучи может быть выполнена за время O(logV ). Таким образом всего получаем O (V logV +E logV )=O(E logV ).

Лучшую оценку можно получить, если использовать фибоначчиевы кучи. С помощью фибоначчиевых куч можно выполнить операцию EXTRACT-MIN за учетное время O(logV ), а операцию DECREASE-KEY – за учетное время O(1). В этом случае суммарное время работы алгоритма Прима составит O (E +V logV ).

4. Составление программы

алгоритм остовной дерево программа

Интерфейс программы (приложение А, В) должен быть следующим. Сначала пользователь вводит порядок графа, чтобы программа могла сформировать таблицу ввода данных (матрица весов) с соответствующим количеством строк и столбцов. При этом все кнопки, кроме кнопки «Сделать таблицу» недоступны для пользователя. Затем пользователь вводит в таблицу данные, при этом он может оставлять пустые ячейки в таблице. Программа будет интерпретировать это как отсутствие ребра между вершинами. Когда данные будут введены, нужно нажать на кнопку «Рассчитать дерево», которая после создания программой таблицы станет активной. Программа рассчитает матрицу весов для минимального остовного дерева и нарисует искомый граф (длины ребер графа не будут соответствовать матрице весов). При этом таблица ввода и все кнопки, кроме кнопки «Продолжить», станут недоступны для пользователя. При нажатии на эту единственную активную кнопку программа перейдет в исходное состояние.

Теперь о том, как программа реализует алгоритм Прима.

Сначала программа создает некий массив a[10] [10] (предполагается, что число вершин графа меньше или равно 10). Этот массив инициализируется: каждому a[i] [j] присваивается 1000 (предполагается, что максимальная длина ребра меньше 1000). Потом данные из таблицы ввода копируются в массив. При этом если в ячейке таблицы ничего не содержится в массив ничего не копируется. Затем делается цикл, который прерывается только тогда, когда все элементы массива станут снова равны 1000. Как работает цикл? Сначала находится минимальный элемент массива (из области выше главной диагонали матрицы ввода). Он запоминается (переменная buf) и ему присваивается 1000. Согласно алгоритму Прима, если ребро подходящее минимальный элемент вычеркивается, а цикл начинается с начала. Подходящее ребро или нет? Ответ на этот вопрос находится следующим образом. Создается массив в n элементов. Каждый элемент равен 1 или 0. Когда вершина включается в дерево, в элемент массива с ее номером записывается 1 (изначально все элементы массива, кроме первого равны 0). Чтобы определить подходящее ребро или нет, нужно посмотреть, находятся ли единицы в массиве (номера элементов равны номерам вершин ребра). Если номерам вершин ребра соответствуют обе единица, значит, ребро не подходящее. Если это условие не выполняется – ребро подходящее. Алгоритм прекращает работу, когда все вершины включены в новый граф.

Отдельно можно выделить процедуру рисования графа. Программа создает двумерный массив координат вершин графа (krug[2] [10]). Вершины располагаются на окружности на одинаковом расстоянии друг от друга. Такой способ очень удобный, потому что не надо беспокоиться о том, что ребра будут наслаиваться одно на другое.

5. Тестирование программы