Fandom

Math Wiki

Prim's algorithm

1,010pages on
this wiki
Add New Page
Talk0 Share

Prim's algorithm is a common method for finding a minimal spanning tree of a connected, weighted, undirected graph. It is a greedy algorithm and, surprisingly, is always correct despite its simplicity. It is not hard at all to execute this algorithm with pencil and paper. However, its proof is a little more involved.

Algorithm

Let G = (V,E) be a connected undirected graph, let w(e) be a bijection from its edges to their weights and let T = (V_n,E_n) be a graph that will form a minimal spanning tree of G, where V_n and E_n are initially empty.

Initial Stage

  1. Select an edge e \in E such that e minimizes w(e). If there is more than one choice, pick out any one arbitrarily. Add e to E_n and add its endpoints to V_n.

Iterative Stage

  1. Select an edge e \in E - E_n adjacent to T such that e minimizes w(e). As before, if there is more than one edge that minimizes weight, the choice is arbitrary. Add e to E_n and add the endpoint of e that is not currently in V_n to V_n.
  2. Repeat previous step until |E_n| = |V| - 1, i.e. until the minimal spanning tree has one less edge than the number of vertices. This step indicates the algorithm is complete, since a tree with n vertices necessarily has n-1 edges.

See Also

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.