Алгоритм Прима
Итак, рассмотрим алгоритм Прима определения минимального по стоимости остовного леса взвешенного связного неориентированного графа 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 – его взвешенная матрица смежностей.




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