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.
How to Run Prim’s Algorithm
Step 1: Choose a random node and highlight it. For this example, I’m choosing node C.
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.
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).
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:
- Come from all of the highlighted nodes.
- 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.
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!