**Prim's algorithm** is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it will only find a minimum spanning tree for one of the connected components. The algorithm was conceived by computer scientist Robert Prim in 1957.

It works as follows:

- create a tree containing a single vertex, chosen arbitrarily from the graph
- create a set containing all the edges in the graph
- loop until every edge in the set connects two vertices in the tree
- remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
- add that edge to the tree

Let *P* be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since *P* is connected, there will always be a path to every vertex. The output *Y* of Prim's algorithm is a tree, because the edge and vertex added to *Y* are connected to other vertices and edges of *Y* and at no iteration is a circuit created since each edge added connects two vertices in two disconnected sets. Also, *Y* includes all vertices from *P* because *Y* is a tree with n vertices, same as *P*. Therefore, *Y* is a spanning tree for *P*.

Let *Y _{1}* be any minimal spanning tree for

Let *Y _{2}* be the tree obtained by removing

Other algorithms for this problem include Kruskal's algorithm, and Boruvka's algorithm.