Prim algorithm, an algorithm in graph theory, can search the minimum spanning tree in the weighted connected graph. In other words, the tree formed by the subset of edges searched by this algorithm not only contains all vertices in the connected graph, but also has the smallest sum of the weights of all edges. This algorithm was discovered by Czech mathematician Vojtek Jarnik in 1930. It was independently discovered by American computer scientist Robert 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.

Simple description of the algorithm

1). input: a weighted connected graph, in which the vertex set is v and the edge set is e;

2). Initialization: Vnew = {x}, where x is any node (starting point) in the set V and Enew = {} is empty;

3). Repeat the following operations until Vnew = V:

A, selecting the edge with the minimum weight in the set E.

B. Add V to the set Vnew and add

4) Output: Use sets Vnew and Enew to describe the minimum spanning tree.

time complexity

Here, the number v of vertices and the number e of edges are recorded.

Adjacency matrix: O(v2) adjacency list: O(elog2v)