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

Алгори́тм При́ма, алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе. Впервые предложен в 1930 г. В. Ярником и позднее переоткрыт Р. Примом (Prim. 1957. P. 1389–1401).

Алгоритм Прима является жадным. ${\displaystyle E}$ и ${\displaystyle V}$ обозначают множества рёбер и вершин графа ${\displaystyle G}$, ${\displaystyle \vert E\vert }$ и ${\displaystyle \vert V\vert }$ – число рёбер и вершин в графе ${\displaystyle G}$ соответственно. Алгоритм строит (^[1] C. 670) минимальное остовное дерево, добавляя к изначально пустому множеству рёбер по ребру на каждой итерации, пока не получится остовное дерево. При этом на каждой итерации под номером ${\displaystyle i,1\leq i\leq |V|-1}$ алгоритма образуется дерево ${\displaystyle T_{i}}$. А добавляемое ребро выбирается так, чтобы минимизировать вес дерева ${\displaystyle T_{i}}$. На начальной итерации алгоритма Прима произвольным образом выбирается вершина, которой должно быть инцидентно первое ребро.

При реализации алгоритма с использованием очереди с приоритетами его временна́я сложность составляет ${\displaystyle O(\vert E\vert \log \vert V\vert )}$ (Алгоритмы. 2013. С. 670). Реализация с использованием фибоначчиевых пирамид сокращает сложность алгоритма до ${\displaystyle O(\vert E\vert +\vert V\vert \log \vert V\vert )}$ (Алгоритмы. 2013. С. 673).

См. также «О большое».