Алгоритм Прима
Итак, рассмотрим алгоритм Прима определения минимального по стоимости остовного леса взвешенного связного неориентированного графа G=(V, E) с функцией веса ребер w. Подход, используемый в этом жадном алгоритме, состоит в непрерывном добавлении ребер к E’ E таким образом, что E’ всегда представляет дерево, являющееся поддеревом некоторого минимального остовного дерева графа G. Первоначально выбирается произвольная вершина r  V как корневая вершина дерева, которое будет построено. Это может быть любая вершина исходного графа, поскольку в конечном итоге все вершины должны быть включены в каркас. Далее для инициализации E’ используется ребро (r, u), имеющее минимальный вес среди ребер, инцидентных r. В продолжение алгоритма выбирается ребро минимального веса между какой-либо вершиной текущего дерева, представленного в E’, и некоторой вершиной, не принадлежащей текущему дереву, и это ребро добавляется к E’. Таким образом каркас минимального веса наращивается путем выбора новой вершины и ребра, которые гарантированно попадают в остовное дерево минимального веса.
Приведем последовательную реализацию алгоритма Прима. Для нее необходимы две множественные величины. Первоначальным значением одной из них являются все вершины графа, а второе множество пусто. Если ребро (vi, vj) включается в каркас, то вершины (их номера i и j) добавляются во второе множество. Очевидно, что алгоритм должен выполняться до тех пор, пока не будут выбраны все вершины (пока множества не совпадут).
Пусть G = (V, E, w) – взвешенный неориентированный граф, для которого необходимо найти минимальное остовное дерево, и пусть A – его взвешенная матрица смежностей.




Прочные и удобные в обращении окна ПВХ г. Чехов прекрасно изолируют помещение от лишнего шума, пыли и насекомых.

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




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

Анализ алгоритма нахождения каркаса минимального веса: последовательная и параллельная реализации
Допустим, необходимо проложить кабель по территории университета, связав все его здания, так, чтобы из каждого здания кабель по какому-либо пути доходил до любого другого здания. Кроме того, предположим, что надо минимизировать общую длину прокладываемого кабеля. Если рассматривать здания как вершины, а кабели между зданиями как ребра, то эта работа с прокладыванием кабеля превращается в задачу определения каркаса, охватывающего здания территории университета, в котором общая длина проложенного кабеля должна быть минимальной. Такую задачу называют нахождением каркаса минимального веса.
Определим понятие каркаса более формально. Если дан связный неориентированный граф G=(V, E), то каркас (также называемый остовным или стягивающим деревом) T=(V, E’), где E’E – это связный граф без циклов. Иными словами, каркас неориентированного графа G – это подграф графа G, дерево, содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же набор вершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно |V|–1 ребро.
Предположим, что для каждого ребра eE существует вес w(e), причем такой вес может выражать, например, цену, длину или время, необходимое для прохода по ребру (в нашем примере – длину кабеля между зданиями). Во взвешенном графе вес подграфа – это сумма весов его ребер. Тогда каркас T минимального веса (или минимальное остовное дерево) – это каркас G, в котором вес дерева минимизирован относительно всех остовных деревьев G. Интуитивно определяется, что вес дерева T=(V, E’) равен




доставка по Москве и Московской области