7.1. Алгоритмы построения минимальных связывающих деревьев
Для построения МСД разработан ряд полиномиальных алгоритмов.
7.1.1. Алгоритм Прима
Алгоритм Прима (R.C. Prim) относится к так называемым "жадным" алгоритмам. Жадные алгоритмы действуют, используя в каждый момент лишь часть исходных данных и принимая лучшее решение на основе этой части. В нашем случае мы будем на каждом шаге рассматривать множество ребер, допускающих присоединение к уже построенной части связывающего дерева, и выбирать из них ребро с наименьшим весом. Повторяя эту процедуру, мы получим остовное дерево с наименьшим весом.
Начнем с произвольной вершины графа xi и включим ее в остовное дерево. Из всех вершин, соединенных с данной (xjГxi), ищем вершину, соединенную ребром с наименьшим весом. Это ребро вместе с новой вершиной добавляется в дерево. Из вершин, не вошедших в дерево, ищем вершину, соединенную с уже построенной частью остовного дерева ребром с наименьшим весом. Это ребро вместе с новой вершиной добавляется в дерево и т. д. После того, как в дерево попадут все вершины, работа будет закончена.
Пример. Исходный взвешенный граф изображен на рис.7.1 (а).
Рисунок 7.1. Исходный граф (а) и ребра–кандидаты (б)
Ребра, вошедшие в дерево, на рисунках будем отмечать жирной линией.
В начале процесса выбираем произвольную вершину, например, х1. Выбираем вершины, непосредственно связанные с х1 (рис.7.1.(б)). Ребро наименьшего веса связывает вершины х1 и х2, поэтому к уже построенной части МСД добавляется вершина х2 вместе с ребром (х1 х2). При добавлении к дереву вершины х2 необходимо определить, не следует ли добавить в кандидаты новые ребра. В результате обнаруживаем, что это необходимо проделать с ребрами (х2 х5) и (х2 х7). Здесь же необходимо проверить, являются ли ребра, ведущие из вершины х1, в х3, х4 и х7, кратчайшими среди ребер, соединяющих эти вершины с деревом, или есть более удобные ребра, исходящие из х2. Ребро (х2 х4) короче ребра (х1 х4), и поэтому необходимо его заменить (рис.7.2.(а)).
б
а
Рисунок 7.2. Добавление ребра (х1 х2) (а) и ребра (х2 х5) (б)
Наименьший вес из пяти ребер - кандидатов имеет ребро (х2 х5), поэтому к дереву нужно добавить его и вершину х5 (рис. 7.2 (б)). Вес ребра (х5 х7) меньше веса ребра (х2 х7), поэтому оно замещает последнее. Из четырех ребер, инцидентных построенной части дерева, наименьший вес имеет ребро (х1 х3), поэтому следующим к дереву добавляется оно и вершина х3 (рис. 7.3 (а)).
Затем к дереву добавляется ребро (х1 х6) вместе с вершиной х6. Поскольку вес ребра (х4 х6) меньше веса ребра (х2 х4), а вес ребра (х6 х7) меньше веса ребра (х5 х7), меняем ребра – кандидаты (рис. 7.3 (б)).
а
б
Рисунок 7.3. Добавление в дерево ребра (х1 х3) (а) и ребра (х1 х6) (б)
Ребро (х4 х6) имеет наименьший вес среди оставшихся, и оно добавляется следующим (рис. 7.4 (а)).
Теперь осталось добавить к дереву всего одно ребро (х6 х7) (рис. 7.4 (б)). После этого процесс завершается, построено МСД с суммарным весом ребер 21.
Рисунок 7.4. Добавление ребра (х4 х6) (а) и ребра (х6 х7) (б)
Сложность алгоритма Прима равна O(m3), где m = X.