Алгоритм Примы

[mexxanoid]

Найти минимальный остов графа, используя алгоритм Прима.
Алгоритм Прима отличается от алгоритма Краскала только тем, что на каждом этапе строится не просто ациклический граф, а дерево.

А л г о р и т м П р и м а

Данные: матрица весов С(G) графа G.
Результат: матрица весов полученного остова, величина мини-мального остова.
1. Выберем в графе G ребро х = v,w минимального веса и постро-им дерево G1 = (V1,X1), полагая V1 = {v,w}, X1 = {х}.
2. Если дерево Gк уже построено и k < n-1, то среди ребер, соеди-няющих вершины этого дерева с вершинами графа G, не входя-щими в Gк , выбираем ребро y минимального веса. Строим дере-во Gк+1, присоединяя к Gк ребро y вместе с его не входящим в Gк концом.



Реализовать на с++ либо н а чем угодно с описание алгоритма
Спасибо

[Stepler]

писал точно такое задание неделю назад, готов продать исходник, количество вершин регулируется пользователем, программа написана на сишке.
впрочем если надумаеш стучись, аська в профиле.