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

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

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

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