Save this video free

Spanning Trees

Kent Quanrud · 1:11:59 · Watch on YouTube

Part of Purdue University Fundamental Algorithms (Fall 2026). See all 18 lectures and search them

These notes were made with YouTube Collector. Paste any YouTube link and get the same: a summary, chapters and a searchable transcript.

Overview

Kent Quanrud develops spanning-tree algorithms from graph definitions and counting arguments, then shows how duality between forests and spanning sets turns locally maximal or minimal solutions into global optima. For weighted graphs with distinct edge weights, he characterizes edges that belong to every minimum spanning tree and uses that property to justify Kruskal's, Borůvka's, and Prim's algorithms, including their main running-time bounds.

Key takeaways

Chapters

0:00 Minimum-Wire Connections and the Spanning-Tree Goal
6:20 Forests, Trees, and What It Means for Edges to Span
12:40 Counting Components to Bound Forest Size
22:15 Why Spanning Sets Need at Least n Minus 1 Edges
27:45 Maximal Forests, Minimal Spanning Sets, and Global Optimality
34:40 Proving the Forest and Spanning-Set Duality
35:30 Weighted MSTs and the Good-Edge Criterion
47:10 Why Good Edges Characterize Minimum Spanning Trees
53:35 Cut Certificates for Identifying Good Edges
56:35 Kruskal's Algorithm: Add Edges in Increasing Weight Order
1:01:50 Prim's Algorithm: Grow One Tree with the Lightest Outgoing Edge
1:04:35 Disjoint-Set Union Speeds Up Kruskal's Cycle Checks
1:07:30 Borůvka's Algorithm and Its Logarithmic Number of Rounds
1:09:20 MST Running-Time Comparison and Faster Algorithms

Keep these chapters and the full searchable transcript in your own library.

Transcript excerpt

0:04 Um okay. So yeah. All right. So today we're doing spanning trees and uh we're actually leaving well it'll always be around all this MP completeness and this risk of heart problems but we're also going to be doing a lot more algorithms and how to solve problems and stuff as well. Okay. So so we sort of already hit the peak. I I I mean I think that the MP completeness stuff is probably the deepest stuff just to wrap your mind around and getting used to showing problems are hard instead of just solving them. At least for me, this kind of reverse thinking, it just takes some time to get used to. That's one reason we do a little earlier in the class compared to other classes is to actually give you more time to digest uh uh the materials. But this this might look a little bit more like stuff we were doing before midterm one. So here's the the the basic setup. In fact, this was the

0:52 historical uh motivation apparently in like the 1800s. Um, okay. So, uh here's like a town. I'm really good at drawing houses. And uh you want to connect the town with electricity. Okay. So, you want to connect them with wires. And um let's say like the amount of wire is basically proportional to the length on the on the on the board. Okay. So, so your goal is to choose kind of the the minimum total amount of wire uh to connect all the houses together. That make sense? >> Yeah. Fully connected. So, every house should be able to reach each other like it's, you know, like as if they're all using the same electrical source. >> Yeah.

1:40 >> Or data center, whatever is the There is an algorithm. Yeah, this we're

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.

Want the full transcript?

Save this video in YouTube Collector to get its complete searchable transcript, your own AI summaries, and a library that keeps every video you collect in one place.