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

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

Kruskal's Algorithm for Minimum Spanning Trees

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

← Spanning Trees and Their PropertiesNext lesson: Prim's Algorithm for Minimum Spanning Trees →

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

Cheapest edge first - and this time, greedy is provably optimal.

  • Define a minimum spanning tree
  • Run Kruskal's algorithm edge by edge
  • Detect cycles with a union-find structure
  • Explain why greedy works here but not for the TSP

Transcript

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

Trees, Spanning Trees, and Minimum Cost Networks

Kruskal's Algorithm for Minimum Spanning Trees

This section builds the cheapest possible connected network, using one of the most elegant algorithms in graph theory. Kruskal's algorithm adds edges greedily, cheapest first. And unlike the greedy methods from chapter ten, this one is guaranteed to find the true optimum.

The Opening Problem

Cabling 5 Offices for Less

A regional telecommunications provider needs to connect five office sites with fiber-optic cable, so data can travel between any two sites, directly or indirectly. Cable is expensive, and the cost of each route depends on terrain and distance. So the provider wants the connected layout that costs the least overall. In a connected weighted graph, a minimum spanning tree, or M S T, is a spanning tree whose total edge weight is as small as possible. Like any spanning tree, it has exactly n minus one edges. Kruskal's algorithm builds one edge by edge. Prim's algorithm, in the next section, grows one vertex by vertex.

11.5.1

Kruskal's Algorithm

Here's Kruskal's algorithm. First, sort all the edges from cheapest to most expensive. Start with an empty set of chosen edges. Then scan the edges in sorted order. Add each edge, unless it would create a cycle with the edges already chosen. In that case, discard it. Stop once you have n minus one edges. The chosen edges form a minimum spanning tree. It's called edge-based because its main loop follows one global ordering of the edges. There's no starting vertex, and no growing outward from any particular place.

Why It Works

The Cut Property

Why does always taking the cheapest safe edge give the true minimum? The reason is a standard result called the cut property. Split the vertices into any two groups. Then a cheapest edge crossing between the groups belongs to some minimum spanning tree. Each edge Kruskal accepts joins two pieces that aren't yet connected. And since edges come in sorted order, it's the cheapest remaining edge that does. So by the cut property, every choice is safe. The proof uses an exchange argument: swapping a crossing edge for a cheaper one never raises the total.

11.5.2

Union-Find: Cycle Checks Without Searching

One step still needs detail. How do we tell, quickly, whether an edge would create a cycle? An edge u v closes a cycle exactly when u and v are already connected, by the edges chosen so far. We could search for a path every time, but that repeats a lot of work. A union-find structure, also called a disjoint-set structure, tracks the connected pieces directly. Every vertex starts in its own component. Find returns a representative label for a vertex's component. Two vertices are connected exactly when find gives them the same representative. Union merges two components into one. So for each edge, compare find of u with find of v. If they match, skip the edge. If they differ, add it, and union the two pieces.

Listing 1

Union-Find in Python

Here's a basic union-find in Python. Each vertex stores a parent pointer, and starts out pointing to itself. Find follows parent pointers until it reaches a vertex that points to itself. That's the representative. Union finds both roots. If they're the same, it returns false, since the edge would close a cycle. Otherwise it points the first root at the second, and returns true. Production versions add two refinements, path compression and union by rank. Together they keep both operations extremely close to constant time. The cycle-detection idea doesn't depend on them.

11.5.3

The 5-Site Network

Back to the provider's five sites, A through E. There are seven feasible routes, with costs in thousands of dollars. The network is connected, but not complete. For instance, there's no direct route from A to D. With five sites, a minimum spanning tree uses exactly four of the seven routes. Sorted by cost, the routes are C D at two, B C at three, A B at four, and D E at five. Then come B D at six, A C at seven, and C E at eight.

Table 1

Tracing Kruskal With Union-Find

Here's the trace, with the union-find representatives at the moment each edge is checked. C D: representatives C and D differ, so add it, and union. B C: B and D differ, so add it. A B: A and D differ, so add it. D E: D and E differ, so add it. That's four edges, all we need. The union in our code points the first root at the second, so after the fourth union, every vertex's representative is E. So the remaining edges, B D, A C and C E, each find E at both ends. Each would close a cycle, and each is correctly skipped.

The Result

14,000 Dollars, Provably Minimal

The minimum spanning tree is C D, B C, A B and D E, with total cost two plus three plus four plus five, which is fourteen. That's fourteen thousand dollars. For this graph, there's a direct check that nothing cheaper exists. The tree uses the four cheapest routes, and every spanning tree needs exactly four edges. So no spanning tree can cost less than fourteen. In general, you can't always argue that simply. What guarantees Kruskal's result is optimal every time is the cut property.

11.5.4

Cost, and Why Greedy Is Safe Here

Sorting m edges takes theta of m log m time, and that dominates. The union-find work, with the refinements, costs far less. Since a connected graph has at most about n squared edges, log m is theta of log n. So Kruskal's running time is often written theta of m log n. Now pause on how unusual the guarantee is. Nearest neighbor for the traveling salesman was greedy, and not guaranteed optimal. Greedy coloring was greedy too, and could use more colors than necessary. Kruskal is greedy in exactly the same spirit. Yet it always reaches the true minimum, whatever the tie-breaking. The minimum spanning tree problem's structure makes greedy choices safe, not just convenient.

Table 2

Kruskal Versus Prim, at a Glance

At a high level, here's how Kruskal compares with Prim's algorithm, which comes next. Kruskal considers all edges globally, cheapest first, wherever they sit. Prim grows a single tree outward from one starting vertex. Kruskal uses union-find to detect cycles. Prim uses a priority queue over the edges on the growing tree's frontier. Kruskal fits graphs given as edge lists, especially sparse ones. Prim fits graphs with adjacency information ready for each vertex. Both are correct for the same reason, but their mechanics differ. And the same construction underlies minimum-cost designs for power grids, road networks, and even some clustering methods in data analysis.

Takeaways

Cheapest Safe Edge, Every Time

To summarize. Kruskal's algorithm sorts every edge by weight, adds each one unless it would close a cycle, and stops at n minus one edges. Union-find checks for cycles. An edge closes one exactly when its endpoints already share a representative. Unlike the greedy heuristics of chapter ten, Kruskal's greedy strategy is guaranteed to produce a true minimum spanning tree, by the cut property. And it runs in theta of m log m time, dominated by sorting. Here's something to think about. Suppose two edges have exactly the same weight, so sorting could put either one first. Is Kruskal's algorithm still guaranteed to produce some minimum spanning tree? Is it guaranteed to produce the same one either way? And what does that say about how many different minimum spanning trees one weighted graph can have?

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 Kruskal's Algorithm for Minimum Spanning Trees

What is a minimum spanning tree, and how does Kruskal's algorithm find one?
A minimum spanning tree of a connected weighted graph is a spanning tree whose total edge weight is as small as possible. Kruskal's algorithm sorts all edges from cheapest to most expensive, adds each edge unless it would create a cycle, and stops at n-1 edges. The chosen edges form the tree.
How do you use union-find to check whether an edge creates a cycle in Kruskal's algorithm?
Compare the representatives of the edge's endpoints: if \text{find}(u) = \text{find}(v), the edge uv would close a cycle, so skip it. If they differ, add the edge and call union to merge the two components. Every vertex starts in its own component, so no path search is needed.
Can you show Kruskal's algorithm on a small example?
Take five sites A through E with edges CD=2, BC=3, AB=4, DE=5, BD=6, AC=7, CE=8. Sorted, the first four edges CD, BC, AB, DE each join different components, so all are added. That gives n-1=4 edges with total cost 2+3+4+5=14. BD, AC, and CE would each close a cycle.
Why does the greedy approach work for Kruskal's algorithm but not for the traveling salesman problem?
Greedy works for minimum spanning trees because of the cut property: for any split of the vertices into two groups, a cheapest edge crossing the split belongs to some minimum spanning tree. Each edge Kruskal accepts is therefore a safe choice. Nearest neighbor for the TSP has no such guarantee, so it can miss the optimum.

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 →