Copyright

Prim's Algorithm: Explanation & Examples Video

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Dijkstra's Algorithm: Definition, Applications & Examples

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:04 Prim's Algorithm
  • 1:43 Steps of Prim's Algorithm
  • 2:18 Example
  • 4:02 Lesson Summary
Save Save Save

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed Speed

Recommended Lessons and Courses for You

Lesson Transcript
Instructor: Laura Pennington

Laura has taught collegiate mathematics and holds a master's degree in pure mathematics.

Prim's algorithm is an algorithm used often in graph theory. This lesson will explain what the algorithm is used for, the steps involved in using it, and a real-world example of putting it to practice.

Prim's Algorithm

Suppose that Al is a motivational speaker, and he commonly has to travel between five cities to speak. He wants to know the routes between these cities that have the least gas cost. To get a better idea, he uses a mathematical tool called a graph. In mathematics, a graph is a collection of vertices and edges connecting those vertices.

Al's graph represents the cities as vertices, and the edges between the cities are the routes between those cities. He then labels each edge with the cost of gas for that route. Doing this makes his graph a weighted graph, which is a graph that has numerical values, called weights, assigned to its edges.

Ultimately, he wants to find the cheapest set of routes between the cities. We call this set of routes a minimum spanning tree. Whoa! Wait a second! What's that? Don't worry, it can be explained using a few definitions.

  • A tree is an undirected graph in which there is exactly one path between any two vertices.
  • A spanning tree of a graph is a tree within the graph that contains all of the vertices of the graph and minimum possible number of edges. A graph can have more than one spanning tree.
  • And a minimum spanning tree of a weighted graph, which is also called minimum connectors, is a spanning tree of the graph in which the sum of the weights of the edges is as small as possible.

Now, it makes sense that Al needs to find the minimum spanning tree of his graph. In doing this, he will find the set of routes that have the cheapest gas costs. Now we just need to figure out how to do this!

One nicely stepped-out algorithm for doing this is Prim's algorithm, which a step-by-step process of finding the minimum spanning tree of a weighted graph.

Steps of Prim's Algorithm

The steps of Prim's algorithm are:

  1. Choose a starting vertex for your tree at random and record the vertex in a table.
  2. Find the edge of the least weight that connects the tree to a vertex that is not in the tree, and add it to the tree. Then record the vertices, edges, and the weight of the edges in your table.
  3. Continue this until all of the vertices are in the tree and recorded in your table.

That doesn't sound too hard! Let's do this for Al's graph to help him find the set of routes that have minimal gas cost, and to help us solidify our understanding of how this algorithm works.

Example

Take a look at Al's graph again.


Prim1


To start Prim's algorithm, we choose a starting vertex. This vertex is random, and the same minimum spanning tree will result from the algorithm regardless of which vertex we start at, so let's just pick vertex A. So we say that A is in our tree, and record it in our table.


Prim3


To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support