Построение минимального остовного дерева графа методом Прима

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

Известный алгоритм построения минимального остовного дерева восходит к Войтеху Ярнику (Vojtech Jarnik) [1930]. Он больше известен под именем алгоритма Прима (Robert Prim). Р. Прим независимо от Ярника придумал его в 1956 и представил более подробное и детальное описание, чем первооткрыватель. Еще раз этот алгоритм открыл Эдсгер Дейкстра (Edsger Wybe Dijkstra) в 1958 году, но название осталось за Примом, т. к. у Дейкстры уже был алгоритм с его именем (поиск кратчайших путей в ориентированном графе).

Этот алгоритм можно отнести к группе алгоритмов, построенных на наращивании дерева: существует только одна нетривиальная компонента (остальные представляют собой одиночные вершины), и она постепенно наращивается добавлением «безопасных» ребер. Время работы алгоритма Джарника-Прима может достигать O (E+VlogV) при использовании фибоначчиевых куч.