Районной администрацией принято решение о газификации одного из небольших сел района

Сеть трубопроводов представляет собой остовное дерево.
Построим остовное дерево алгоритмом Прима, в котором поддерживается уже обработанная часть графа (минимального остовного дерева), постепенно расширяемая за счёт ближайших вершин.
Таким образом, для нахождения минимального остовного дерева начинается с произвольной вершины и постепенно добавляются минимальные ребра, не образующие цикл, ближайшие к уже имеющимся.
Построения начинаем с ребра минимального веса (3,5).
Рис . 4. Первый шаг алгоритма Прима
Из ближайших ребер выбираем ребро наименьшего веса, не образующее цикл: (3,2), (5,7), (5,8).
Рис