85 90/

Рис. 7г

к 45

Рис. 7д

50>

85 90/

75>

Предложенный способ хорошо работает и в случае, когда исходная сеть задана при помощи таблицы.

Пример 2. Пусть, например, нужно соединить города А, В, С, Dh Е. Стоимости строительства дорог, соединяющих любые два города, известны

Сеть дорог минимальной стоимости состоит из четырех, 5 - 1=4, дуг и строится так. Сначала выбирается самый дешевый участок дороги - ВС, соединяющий города В и С (его цена равна 6).

Затем он удлиняется на самый дешевый из выходящих из городов В и С - СЕ (его цена равна 8).

На третьем шаге вновь выбирается самый дешевый - это ЕА (его цена равна 7).

Последний участок дороги выбираем так, чтобы не образовалось цикла: соединим для этого город D с ближайшим к нему городом В (его цена равна 9).

Таким образом, минимальная стоимость строительства сети равна 6 + 8 + 7 + 9 = 30 (рис. 8).

Рис. 8

Описание алгоритма

Опишем алгоритм, предложенный Примом ([8], с. 272), считая, что число вершин заданного графа п £ 2. Этот алгоритм приводит к искомому результату за п - 1 шаг.

1-й шаг. Пометим произвольную вершину графа. Из ребер звезды, порожденной этой вершиной, выберем ребро наименьшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результате две вершины графа оказываются помеченными.

Если других вершин в графе нет, то искомое порождающее дерево построено (обозначим его через J{) и поставленная задача решена. В противном случае потребуется новый шаг. Опишем его.