Алгоритм Прима — это алгоритм, способный построить самое маленькое остовное дерево для взвешенных связных неориентированных графов.
Введение
Алгоритм Прима является самым простым для осуществления из всего набора алгоритмов поиска MST (Minίmum Spannίng Trȇe) и его рекомендуют использовать для насыщенных графов. В нем должно использоваться сечение графа, которое состоит из вершин деревьев, выбранных для MST, и вершин, которые не являются древесными, то есть, еще не выбранных в дерево MST. Сначала следует выбрать в качестве дерева MST любую из вершин, а далее нужно поместить в MST самое маленькое ребро, являющееся перекрестным и превращающее не древесную вершину дерева MST в древесную, и повторить эту процедуру V— 1 количество раз, то есть, до тех пор, пока каждая из вершин не будет добавлена в дерево.
Это описание является, по сути, примитивной реализацией алгоритма Прима. Для того чтобы отыскать следующее ребро для включения его в MST, нужно осуществить просмотр всех ребер, выходящих из древесной вершины в не древесную вершину, а далее осуществить выбор из них самого короткого и включить его в MST.
Алгоритм Прима
В качестве единичного шага в алгоритме Прима используется прибавление вершины в дерево MST. Здесь главным является поиск кратчайшего расстояние от каждой не древесной вершины до дерева. Когда выполняется присоединение вершины v к дереву, то единственно возможным изменением для не древесных вершин w считается их приближение к дереву. То есть, нет необходимости в проверке расстояния от вершины w и до каждой вершины дерева, хватит и определения минимального расстояния на текущий момент и проверки, способно ли изменить добавление вершины v к дереву это минимальное расстояние.
Для того чтобы реализовать этот алгоритм, необходимо наличие определенных информационных структур, которые могут предоставить следующие данные:
- набор ребер дерева,
- наименьшее по размерам дерево, которое соединяет вершину, не являющуюся древесной, с деревом,
- длину данного ребра.
Самой простой реализацией каждой из таких структур, данных может считаться вектор, который проиндексирован именами вершин. Такой вектор может использоваться для хранения древесных ребер, осуществляя индексацию по вершинам при их добавлении в дерево. Алгоритм Прима для насыщенных графов может быть реализован программно. Такая программа должна использовать для перечисленных выше структур данных векторы mst, fr и wt.
После того как в дерево включено новое ребро (и вершина), следует решить еще следующие задачи:
- Выполнить проверку приближения какой-либо из не древесных вершин к дереву при добавлении нового ребра.
- Отыскать следующее ребро, подлежащее включению в дерево.
Реализовать программно решение этих задач можно при помощи одного просмотра не древесных вершин. Сначала программа должна обновить величины векторов wt$[$ w$]$ и fr$[$ w$]$, если v-w способен приблизить w к дереву, то есть, изменяется существующий минимум, если wt$[$ w$]$ (размер fr$[$ w$]$) может показать, что w ближе к дереву, чем любая другая не древесная вершина с меньшим индексом.
Эта программная реализация алгоритма Прима может быть рекомендована для обработки насыщенных графов и применяется для любого представления графа, в котором возможна проверка наличия указанного ребра. Внешний цикл выполняет наращивание MST-дерева, путем выбора минимальных ребер, пересекающих сечение между вершинами, входящими в MST, и вершинами, которые не входят в него. Цикл по w должен отыскать минимальное ребро, не нарушая (если w не содержится в MST) условие, что ребро fr$[$ w$]$ считается наиболее коротким (с весом wt$[$ w$]$) ребром из w в MST
Итогом вычислений должен стать вектор указателей на ребра. Первый указатель (mst$[$ 0$]$) не должен использоваться, остальные (от mst$[$ 1$]$ до mst$[$ G.V()$]$) должны содержать MST-дерево связного элемента графа, которому принадлежит нулевая вершина.
tȇmplate $\lt$clàss Gràph, clàss Edgȇ>
clàss MST
{ cŏnst Gràph &G;
vȇctor$\lt$doublȇ> wt;
vȇctor$\lt$Edgȇ *> fr, mst;
publίc:
MST(cŏnst Gràph &G) : G(G),
mst(G.V()), wt(G.V(), G.V()), fr(G.V())
{ ίnt mίn = -1;
for (ίnt v = 0; mίn != 0; v = mίn)
{ mίn = 0;
for (ίnt w = 1; w $\lt$ G.V(); w++)
ίf (mst$[$ w$]$ == 0)
{ doublȇ P; Edgȇ* ȇ = G.edgȇ(v, w);
ίf (ȇ)
ίf ((P = ȇ->wt()) $\lt$ wt$[$ w$]$)
{ wt$[$ w$]$ = P; fr$[$ w$]$ = ȇ; }
ίf (wt$[$ w$]$ $\lt$ wt$[$ mίn$]$) mίn = w;
}
ίf (mίn) mst$[$ mίn$]$ = fr$[$ mίn$]$;
}
}
voίd shŏw()
{ for (ίnt v = 1; v $\lt$ G.V(); v++)
ίf (mst$[$ v$]$) mst$[$ v$]$->show();
}
};
Алгоритм Прима способен найти MST для насыщенного графа за линейное время. Этот алгоритм может также использоваться для вычисления MST.
Первым этапом вычисления MST-дерева по алгоритму Прима является занесение в это дерево нулевой вершины. Далее следует найти все ребра, которые могут соединить нулевую вершину с другими вершинами, еще не состоящими в этом дереве, и выбрать из них самое короткое (слева вверху), как показано на рисунке ниже:
