PRIM'S ALGORITHM

Domain	Definition
Math	An algorithm for computing a minimum spanning tree. It builds upon a single partial minimum spanning tree, at each step adding an edge connecting the vertex nearest to but not already in the current partial minimum spanning tree. (references)
Source: compiled by the editor from various references; see credits.

Specialty Definition: Prim's algorithm

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

Prim's algorithm can be shown to run in time which is O (m + n log n) where m is the number of edges and n is the number of vertices.

Proof

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₁ be any minimal spanning tree for P. If Y = Y₁, QED. If not, there is an edge in Y that is not in Y₁. Let e be the first edge that was added when Y was constructed. Let V be the set of vertices of Y - e. Then one endpoint of e is in Y and another is not. Since Y₁ is a spanning tree of P, there is a path in Y₁ joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in V to one that is not in V. Now, at the iteration when e was added to Y, f could also have been added and it would be added instead of e if its weight was less than e. Since f was not added, we conclude that w(f) >= w(e).

Let Y₂ be the tree obtained by removing f and adding e from Y₁. It shows that Y₂ is a tree that is more common with Y than with Y₁. If Y₂ equals Y, QED. If not, we can find a tree, Y₃ with one more edge in common with Y than Y₂ and so forth. Continuing this way produces a tree that is more in common with Y than with the preceding tree. Since there are finite number of edges in Y, the sequence is finite, so there will eventually be a tree, Y_h, which is identical to Y. This shows Y is a minimal spanning tree.

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

Anagrams: PRIM'S ALGORITHM

Scrabble® Enable2K-Verified Anagrams
	Words within the letters "'-a-g-h-i-i-l-m-m-o-p-r-r-s-t"
	-5 letters: algorithms, immoralist, logarithms, misprogram.
Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro.