Алгоритм Прима
На вход алгоритма подаётся связный неориентированный граф.
Для каждого ребра задаётся его стоимость.
Выбираем произвольную вершину в качестве начальной.
Она будет первой вершиной, включенное в искомое остовное дерево.
Множество вершин графа можно разделить на два подмножества:
- подмножество состоящее из вершин уже построенного остовного дерева
- остальные вершины графа.
Сортируем массив рёбер по весу в порядке возрастания.
Каждый раз добавляем к остовнуму дереву ребро с минимальным весом,
одна вершина которого уже включена в остовное дерево, а вторая нет.
Ребро включается в остовное дерево, а вторая вершина переносится
в множество вершин остовного дерева. Рост дерева происходит до тех пор,
пока не будут исчерпаны все вершины исходного графа.
Алгоритм.
- Множество остовных вершин – исходная вершина
- Множество оставшихся - все вершины за исключением исходной.
- Пока множество оставшихся не пусто
- Ищем ребро соединяющее множество остовных и множество оставшихся
и имеющее наименьший вес.
- Для найденного ребра, вершину принадлежащую множеству оставшихся:
- удаляем из множества оставшихся.
- добавляем к множеству остовных.
Над множествами вершин будут выполняться операции поиска, вставки и удаления.
Наиболее подходящей структурой для этих операций является сбалансированное
бинарное дерево – AVL дерево или красно-чёрное. Время работы всех операций O(log(n)).
К сожалению, библиотека stl по непонятным причинам не имеет соответстующих классов.
В приведённой здесь программе для представления множеств используется класс vector.
Граф, используемый в примере изображён на рисунке.
