Пусть некоторое семейство пунктов требуется связать сетью дорог. Известна стоимость прокладки дороги между теми парами пунктов, для которых это возможно. Стоимость прокладки сети дорог должна быть минимальной.
Естественно, сеть дорог должна быть связной (любой пункт должен быть доступен из любого другого). В сети не должно быть циклов (иначе стоимость прокладки можно уменьшить, исключив строительство какой-нибудь дороги из цикла). Отсюда следует, что оптимальная сеть дорог является остовным подграфом исходного графа потенциальных дорог. Таким образом, задача построения остовного дерева в неориентированном графе, минимального по суммарному весу дуг, является естественной.
Известно множество эффективных алгоритмов решения этой задачи. В основном они были разработаны в середине 20 века. Приведем один из них – алгоритм Прима.
Суть этого алгоритма в следующем. На каждой итерации вершины разбиты на два класса. Вершины первого класса уже включены в дерево. Добавляется в дерево та вершина из второго класса, для которой минимален вес дуги до вершин второго класса.
Технически этот подход, как и в алгоритме Дейкстры, реализуется приданием вершинам пометок. У вершин первого класса они постоянные, у остальных – временные. В данном случае удобно, чтобы пометки состояли из двух частей: вторая это минимальный из весов дуг, соединяющих данную вершину с временной пометкой до вершин с постоянными пометками, первая – номер той вершины с постоянными пометками, для которой этот минимум достигается.
Сформированную часть дерева будем обозначать через ГS=(US,ES). Далее для обозначения вершин будут использоваться их номера.
Шаг 0 (инициализация). US={1}, ES=Æ. (Вообще говоря, в качестве начальной вершины дерева можно принять любую вершину.) Все вершины кроме первой снабжаем пометками [1,c(1,i)] (вторая часть пометки – вес дуги между первой и i-й вершинами). Далее пометку i-й вершины обозначаем [a(i),b(i)].
Шаг 1. Находим вершину j* с временной пометкой с минимальным значением b(i). Положим
US:=USÈ{j*}, ES:=ESÈ( j*,a( j*)).
Пометка вершины j* становится постоянной.
Шаг 2. Если |US|=p (т.е. все вершины включены в дерево) то конец иначе переход к шагу 3.
Шаг 3 (обновление пометок). Если для jÏUS (b(j)>c(j,j*)) то (b(j):=c(j,j*), a(j):= j*). Переход к шагу 1.
Этот алгоритм также удобно реализовывать в виде таблицы.