Statistics How To

Prim’s Algorithm: Simple Definition, How to Run (in Easy Steps)

Statistics Definitions > Prim’s Algorithm

If you aren’t familiar with trees or minimum spanning trees, you may want to read this article first: What is a Minimum Spanning Tree?

What is Prim’s Algorithm?

Prim’s algorithm is a way to find a minimum spanning tree (MST). A minimum spanning tree is a specific tree graph that minimizes the lengths (weights) of the tree’s edges.

prim's algorithm

A minimum spanning tree (shown in red) minimizes the edges (weights) of a tree.



How to Run Prim’s Algorithm

Step 1: Choose a random node and highlight it. For this example, I’m choosing node C.
prim 1a

Step 2: Find all of the edges that go to un-highlighted nodes. For this example, node C has three edges with weights 1, 2, and 3. Highlight the edge with the lowest weight. For this example, that’s 1.
prim 2a

Step 3: Highlight the node you just reached (in this example, that’s node A).

Step 4: Look at all of the nodes highlighted so far (in this example, that’s A And C). Highlight the edge with lowest weight (in this example, that’s the edge with weight 2).
prim 3a

Note: if you have have more than one edge with the same weight, pick a random one.

Step 5: Highlight the node you just reached.

Step 6: Highlight the edge with the lowest weight. Choose from all of the edges that:

  1. Come from all of the highlighted nodes.
  2. Reach a node that you haven’t highlighted yet

Step 7: Repeat steps 5 and 6 until you have no more un-highlighted nodes. For this particular example, the specific steps remaining are:

  • a. Highlight node E.
  • b. Highlight edge 3 and then node D.
  • c. Highlight edge 5 and then node B.
  • d. Highlight edge 6 and then node F.
  • e. Highlight edge 9 and then node G.
  • The finished graph is shown at the bottom right of this image:
    prim 4

    That’s it!

    If you prefer an online interactive environment to learn R and statistics, this free R Tutorial by Datacamp is a great way to get started. If you're are somewhat comfortable with R and are interested in going deeper into Statistics, try this Statistics with R track.

    Comments are now closed for this post. Need help or want to post a correction? Please post a comment on our Facebook page and I'll do my best to help!
    Prim’s Algorithm: Simple Definition, How to Run (in Easy Steps) was last modified: October 15th, 2017 by Andale