Prim's Algorithm for Minimum Spanning Trees | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 11.6 Free with a free account

Prim's Algorithm for Minimum Spanning Trees

Discrete Mathematics · Chapter 11: Trees, Spanning Trees, and Minimum Cost NetworksSection 11.6 · lesson 76 of 878 min · free with a free account

← Kruskal's Algorithm for Minimum Spanning TreesNext lesson: Introduction to Matrices →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Grow the network outward, one cheapest link at a time.

  • State Prim's algorithm and its frontier edges
  • Trace Prim's algorithm with a priority queue
  • Contrast vertex-based Prim with edge-based Kruskal
  • Choose between them by density and use

Transcript

Everything said in the video, section by section (1,078 words). Read along, or search it.

Trees, Spanning Trees, and Minimum Cost Networks

Prim's Algorithm for Minimum Spanning Trees

This section closes chapter eleven with the second classic minimum spanning tree algorithm. Prim's algorithm grows a network outward from wherever it already stands, one cheapest link at a time. It reaches the same kind of optimal answer as Kruskal's algorithm, by a genuinely different mechanism.

The Opening Problem

Building Out From a Data Center

A fiber-optic provider already has one data center, H, up and running, and needs to extend service to four nearby towns. The costs of every feasible link are surveyed in advance. Kruskal's approach looked at every possible connection across the whole map before choosing. But these crews work outward from the data center that already exists. At each stage, they ask a narrower question. Of all the links that would extend the current network to exactly one new site, which is cheapest? They build it, and ask again from the bigger network. That's Prim's algorithm. And like Kruskal's, it always produces a minimum spanning tree.

11.6.1

Prim's Algorithm

Here's the algorithm. Start with a tree, T, containing only a chosen start vertex. A frontier edge is an edge with exactly one endpoint in T, and the other outside. Repeatedly add the cheapest frontier edge to T, which brings its outside endpoint into the tree. Stop when T spans every vertex. Notice what's never considered. An edge between two vertices both outside T, or both already inside T, is never a candidate. So growth happens by admitting one new vertex at a time to a single tree, which is connected at every step. That's what makes Prim's algorithm vertex-based.

The Code

Prim's Algorithm With a Min-Heap

In Python, a min-heap holds the frontier edges, as weight, inside vertex, outside vertex. The heap always returns the cheapest one first. At each step, pop the cheapest edge. If its outside vertex is already in the tree, both ends are inside, so it's not really a frontier edge anymore. Skip it. Otherwise, add that vertex and edge to the tree, and push the new vertex's edges to vertices still outside. The loop ends once every vertex is visited, returning the tree edges and their total weight.

11.6.3

Running Prim From H

Here's a worked example. The vertices are the data center H and towns P, Q, R and S. The edge costs, in thousands of dollars, are H P one, H Q seven, P Q three, P R six, Q R two, Q S five, and R S four. Start from H. The frontier is H P at one, and H Q at seven. Add H P, bringing in P. That adds P Q at three and P R at six to the frontier. The cheapest of seven, three and six is P Q. Add it, bringing in Q. Now H Q joins two tree vertices, so it drops out. Q R at two and Q S at five join the frontier. The cheapest of six, two and five is Q R. Add it, bringing in R. P R drops out, and R S at four joins. Finally, R S at four beats Q S at five. Add it, and every vertex is in. The minimum spanning tree is H P, P Q, Q R and R S, with total weight one plus three plus two plus four, which is ten.

11.6.2

Same Graph, 2 Edges In

Here's the same graph, twice, after each algorithm has accepted two edges. Prim has taken H P, then P Q. Its accepted edges form one connected tree, H, P and Q. Kruskal sorts all edges first. Its two cheapest are H P at one, and Q R at two. So after two edges, it holds two separate fragments, H P and Q R, with S untouched. That's the structural difference. Kruskal can accept an edge anywhere in the graph, so its partial result can be in pieces. Prim's partial result is always one connected tree.

Kruskal on the Same Graph

Different Route, Identical Tree

Let's finish Kruskal on this graph. The sorted order is H P, Q R, P Q, R S, Q S, P R, H Q. It accepts H P, then Q R, giving two fragments. Then P Q merges them into one. Then R S brings in S. That's four edges, so it's done. Both algorithms end with exactly the same edges, H P, P Q, Q R and R S, and the same total, ten. They discovered those edges in a different order. And Kruskal passed through a temporarily disconnected stage that Prim never does.

Table 1

Kruskal Versus Prim

Here's the full comparison. Kruskal adds the cheapest remaining edge anywhere, if it doesn't close a cycle. Prim adds the cheapest edge leaving the current tree. Kruskal needs a sorted edge list and union-find. Prim needs a priority queue over the frontier. Along the way, Kruskal may hold several disconnected fragments. Prim always holds one connected tree. Kruskal runs in order E log E, dominated by sorting. Prim runs in order E log V with a heap, or order V squared with a plain array. And Kruskal fits sparse graphs stored as edge lists, while Prim fits dense graphs stored as adjacency matrices.

11.6.4

Choosing Between Them

Both always return a correct minimum spanning tree. So choosing between them is about efficiency and convenience, not correctness. Density is the main factor. On a sparse graph, Kruskal's sort stays cheap. On a dense graph, where the number of edges approaches V squared, Prim's array version, at order V squared, beats sorting all those edges. Representation matters too. With an adjacency matrix, Prim just scans rows. With an edge list, Kruskal sorts it directly. And sometimes one requirement settles it. If a valid, connected partial network must exist at every stage, only Prim guarantees that. That's the data center build-out. Crews may need the network to be usable after each phase of construction, so they grow it outward from H.

Takeaways

Grow From Where You Stand

To summarize. Prim's algorithm grows one connected tree by always adding the cheapest frontier edge, the cheapest edge linking the tree to a new vertex. Kruskal's algorithm works from one global sorted order, so its accepted edges may form several fragments before merging. Prim's accepted edges are connected at every step. Both are greedy, both are guaranteed correct, and they can find the very same tree by entirely different routes. Prim tends to suit dense graphs, adjacency matrices, and staged construction. Kruskal tends to suit sparse graphs given as edge lists. Here's something to think about. Prim's algorithm is run twice on the same connected, weighted graph, from two different starting vertices. Must the two runs find the identical spanning tree? And what role, if any, does it play whether the edge weights are all distinct?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Prim's Algorithm for Minimum Spanning Trees

What is Prim's algorithm, and what is a frontier edge?
Prim's algorithm is a greedy method that builds a minimum spanning tree by growing one tree outward from a start vertex, always adding the cheapest frontier edge. A frontier edge has exactly one endpoint in the tree T and the other outside it. Each addition brings in one new vertex, and the algorithm stops when T spans every vertex.
How do you trace Prim's algorithm with a priority queue?
Push the start vertex's edges into a min-heap, then repeatedly pop the cheapest edge, skipping it if its outside vertex is already in the tree. Take edges HP=1, HQ=7, PQ=3, PR=6, QR=2, QS=5, RS=4, starting at H. The accepted edges are HP, PQ, QR, RS, with total weight 1+3+2+4=10.
What is the difference between Prim's and Kruskal's algorithms?
Prim's algorithm is vertex-based: it adds the cheapest edge leaving the current tree, so its partial result is always one connected tree. Kruskal's algorithm is edge-based: it adds the cheapest remaining edge anywhere that does not close a cycle, so its partial result can be several separate fragments. Both end with a minimum spanning tree.
When should I use Prim's algorithm instead of Kruskal's?
Use Prim's algorithm for dense graphs, where the number of edges approaches V^2, especially when the graph is stored as an adjacency matrix. Its array version runs in O(V^2), which beats sorting all those edges. Kruskal's algorithm, which runs in O(E\log E), fits sparse graphs stored as edge lists. Prim's is also the choice if the partial network must stay connected at every stage.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →