Решение задачи о минимальном остовном дереве методом Прима

Необходимо спланировать постройку дорог минимальной стоимости, которые соединили бы N городов так, чтобы из каждого города можно было попасть в любой другой. Для каждой пары городов известна стоимость строительства дороги между ними.

Общая формулировка задачи
Задача о минимальном остовном дереве в общем случае формулируется так: пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин (контактов), а E — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения). w() называется весовой функцией. Задача состоит в нахождении такого связного ациклического подграфа T, содержащего все вершины, что суммарный вес его ребер будет минимален.
Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево T, у которого суммарный вес его ребер минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

1.) Акулич И.Л. Математическое программирование в примерах и задачах. – М. Высш. шк., 1986.
2.) Вентцель Е.С. Исследование операций. – М. Высш. шк., 2001.
3.) Романовский И.В. Дискретный анализ. – СПб.: Невский диалект, 2003.
4.) Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. – М.: Бином Универсал, 1998.