FANDOM


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

Community content is available under CC-BY-SA unless otherwise noted.