В этом алгоритме для хранения вершин каркаса минимального веса во время его построения используется множество VT. Также используется массив d[1..n], в котором для каждой вершины v  (V-VT) d[v] содержит минимальный из весов всех ребер, инцидентных вершинам из VT и вершине v. Сначала VT содержит произвольную вершину r, которая становится корнем минимального остовного дерева. Кроме того d[r] = 0 и для всех v  (V – VT) d[v] = w(r, v), если такое ребро (r, v) существует; иначе d[v] = . На каждой итерации алгоритма в VT добавляется новая вершина u такая, что d[u] = min{d[v]v  (V – VT)}. После добавления этой вершины все значения d[v] для v  (V – VT) обновляются, потому что может появиться ребро с меньшим весом между вершиной v и только что добавленной вершиной u. Выполнение алгоритма заканчивается, когда V = VT. На рис. 2 проиллюстрирована работа этого алгоритма. По окончании работы стоимость минимального остовного дерева равна vV d[v]. Добавим также, что данный алгоритм легко модифицировать для хранения ребер, входящих в каркас минимального веса.
В Алгоритме 1 тело цикла while (строки 10–13) выполняется n – 1 раз. Вычисление min{d[v]v  (V – VT)} (строка 10) и цикл for (строки 12 и 13) выполняются за (n) шагов. Таким образом, общая сложность данной реализации алгоритма Прима равна (n2).



"Железные кони" - верные помощники людей. Большой автомагазин предлагает всем желающим полное описание характеристик интересующих автомобилей.