Если граф G несвязный, он не может иметь остовного дерева, но у него есть остовный лес. Далее по тексту будем считать, что граф G связный. Если G несвязный, то можно найти компоненты связности (существуют различные алгоритмы нахождения компонентов связности, которые можно реализовать как последовательно, так и параллельно, но это выходит за рамки вопросов, рассматриваемых в данной статье) и применить алгоритм нахождения минимального каркаса для каждого из них. Также можно изменить алгоритм нахождения остовного дерева минимального веса, чтобы на выходе получать минимальный остовный лес.
В целом, существует несколько алгоритмов определения минимального каркаса графа, в частности алгоритм Краскала, Прима и Соллина. Во всех трех этих алгоритмах используется жадный подход к решению задачи, т. е. в любой момент выполнения данных алгоритмов существует множество ребер E’, представляющее подмножество некоторого минимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребер выбирается «лучшее» ребро, обладающее определенными свойствами, и добавляется к формируемому каркасу минимального веса. Одним из важных свойств любого ребра, добавляемого к E’, является его безопасность, т. е. то, что обновленное множество ребер E’ будет продолжать представлять подмножество некоторого минимального остовного дерева.
В этой статье будет проведен сравнительный анализ последовательной (для однопроцессорной машины) и одного из вариантов параллельной (для многопроцессорного компьютера) реализаций алгоритма Прима.




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