Алгоритм поиска минимального остовного дерева

МОД для связного графа можно найти с помощью грубой силы. Поскольку множество ребер МОД является подмножеством в множестве ребер исходного графа, можно просто перебрать все возможные подмножества и найти среди них МОД. Нетрудно видеть, что это чрезвычайно трудоемкий процесс. В множестве из N ребер имеется 2^N подмножеств. Алгоритм Дейкстры-Прима В конце 1950-х годов Эдгар Дейкстра и Прим, работая и публикуя свои результаты независимо друг от друга, предложили следующий алгоритм построения МОД. Воспользуемся для поиска МОД так называемым "жадным" алгоритмом. Жадные алгоритмы действуют, используя в каждый момент лишь часть исходных данных и принимая лучшее решение на основе этой части. В нашем случае мы будем на каждом шаге рассматривать множество ребер, допускающих присоединение к уже построенной части остовного дерева, и выбирать из них ребро с наименьшим весом. Повторяя эту процедуру, мы получим остовное дерево с наименьшим весом. Разобьем вершины графа на три класса: вершины, вошедшие в уже построенную часть дерева, вершины, окаймляющие построенную часть, и еще не рассмотренные вершины. Начнем с произвольной вершины графа и включим ее в остовное дерево. Поскольку результатом построения будет некорневое дерево, выбор исходной вершины не влияет на окончательный результат (конечно, если МОД единственно). Все вершины, соединенные с данной, заносим в кайму. Затем выполняется цикл поиска ребра с наименьшим весом, соединяющего уже построенную часть остовного дерева с каймой; это ребро вместе с новой вершиной добавляется в дерево и происходит обновление каймы. После того, как в дерево попадут все вершины, работа будет закончена.

 

На рисунке 1 описано исполнение алгоритма на конкретном примере.

В начале процесса мы выбираем произвольный узел A. Как мы уже говорили, при другом выборе начальной вершины результат будет тем же самым, если МОД единственно.

Исходный граф изображен на рис. 1 (а) и, как уже упоминалось, мы начинаем построение МОД с вершины A. Все вершины, непосредственно связанные с A, образуют исходную кайму. Видно, что ребро наименьшего веса связывает узлы A и B, поэтому к уже построенной части МОД добавляется вершина B вместе с ребром AB. При добавлении к дереву вершины B (рис. 1 (в)) мы должны определить, не следует ли добавить к кайме новые вершины. В результате мы обнаруживаем, что это необходимо проделать с вершинами E и G. Поскольку обе эти вершины соединены только с вершиной B уже построенной части дерева, мы добавляем соединяющие ребра к списку рассматриваемых на следующем шаге. Здесь же необходимо проверить, являются ли ребра, ведущие из вершины A в C, D и F, кратчайшими среди ребер, соединяющих эти вершины с деревом, или есть более удобные ребра, исходящие из B. В исходном графе вершина B не соединена непосредственно ни с C, ни с F, поэтому для них ничего не меняется. А вот ребро BD короче ребра AD, и поэтому должно его заменить. Наименьший вес из пяти ребер, идущих в кайму, имеет ребро BE, поэтому к дереву нужно добавить его и вершину E (рис. 1 (г)). Вес ребра EG меньше веса ребра BG, поэтому оно замещает последнее. Из четырех ребер, ведущих в кайму, наименьший вес имеет AC, поэтому следующим к дереву добавляется оно. Добавление к остовному дереву вершины C и ребра AC (рис. 1 (д)) не приводит к изменению списка ребер.

Затем мы выбираем ребро AF и добавляем его к дереву вместе с вершиной F. Кроме того, мы меняем список связей, поскольку вес ребра FD меньше веса ребра BD, а вес ребра FG меньше веса ребра EG. В получившейся кайме (рис. 1 (е)) ребро FD имеет наименьший вес среди оставшихся, и оно добавляется следующим.

Теперь осталось добавить к дереву всего один узел (рис. 1 (ж)). После этого процесс завершается, и мы построили МОД с корнем в вершине A (рис. 1 (з)).