Prim algorithm, an algorithm in graph theory, can search the minimum spanning tree in the weighted connected graph. That is to say, the tree formed by the subset of edges searched by this algorithm not only contains all vertices in the connected graph (English: Vertex (graph theory)), but also has the smallest sum of the weights of all edges.

The algorithm was discovered by Czech mathematician Vojtech Jarnik (English: vojt ch jarník) in 1930. Discovered independently by American computer scientist Robert prim (English: Robert C. Prim) in 1957; 1959, Edsger Dijkstra discovered the algorithm again. Therefore, in some occasions, prim algorithm is also called DJP algorithm, Jarnik algorithm or prim-Jarnik algorithm.

In the simple realization of adjacency matrix graph representation, it takes O(V) running time to find all the minimum weighted edges. Using simple binary heap and adjacency list, the running time of prim algorithm can be reduced to O(ElogV), where E is the number of edges of connected graph and V is the number of vertices. If a complicated Fibonacci reactor is used, the running time can be further shortened to O(E+VlogV), and the running speed can be significantly improved when the connected graph is dense enough (when e meets the ω (vlogv) condition).