Minimum Spanning Trees
Spanning trees connect all nodes with minimum edges. Learn Kruskal's and Prim's algorithms.
Lessons
1. Intro
(Why we need MSTs)
2. What is a Spanning Tree?
(Definition and properties)
3. Minimum Spanning Tree (MST)
(Minimum total edge weight)
4. The Cut Property
Foundation for MST algos
5. The Cycle Property
(Avoiding unnecessary edges)
6. Kruskal's Algorithm - Idea
(Sort edges, add greedily)
7. Kruskal with Union-Find
(Detecting cycles efficiently)
8. Kruskal's Time Complexity
(Sorting dominates)
9. Kruskal's Algorithm - Pseudocode
(Step-by-step implementation)
10. Prim's Algorithm - Idea
(Grow tree from one node)
11. Prim with Priority Queue
(Finding lightest edge fast)
12. Prim's Time Complexity
(Heap operations dominate)
13. Prim's Algorithm - Pseudocode
(Step-by-step implementation)
14. Kruskal vs Prim - When to Use Each
(Choosing the right algorithm)
15. MST in Disconnected Graphs
(Handling multiple components)
16. Problem - Road Reparation
CSES 1675 - MST or impossible
17. Problem - Read Statement
(CSES 1675)
18. Core Idea - Check Connectivity
(MST needs connected graph)
19. Core Idea - Kruskal is Perfect Here
(Sort edges, union components)
20. Algorithm - Kruskal with Validation
(Count edges added)
21. Road Reparation - Implementation
(Kruskal with edge count)
22. Problem - Implement Solution
(CSES 1675)
23. Walkthrough - Road Reparation
(Example execution)
24. Lessons from Road Reparation
(When MST doesn't exist)
25. Problem - Min Cost to Connect All Points
LeetCode 1584 - Complete gr...
26. Problem - Read Statement
(LeetCode 1584)
27. Core Idea - Complete Graph
(n² edges to consider)
28. Core Idea - Manhattan Distance
(Computing edge weights)
29. Algorithm - Prim on Implicit Graph
(Compute edges as needed)
30. Min Cost Connect - Implementation
(Prim with lazy heap)
31. Problem - Implement Solution
(LeetCode 1584)
32. Walkthrough - Min Cost Connect
(Example execution)
33. Lessons from Min Cost Connect
(Implicit vs explicit graphs)
34. Problem - Building Roads
CSES 1666 - MSF for components
35. Problem - Read Statement
(CSES 1666)
36. Core Idea - Find Components
(DSU or DFS)
37. Core Idea - Connect Component Representatives
(Chain them together)
38. Algorithm - Component Chaining
(DSU then connect)
39. Building Roads - Implementation
(DSU and component list)
40. Problem - Implement Solution
(CSES 1666)
41. Walkthrough - Building Roads
(Example execution)
42. Lessons from Building Roads
(MST ideas without weights)
43. MST Uniqueness
(When is MST unique?)
44. Second-Best MST
(Almost minimum spanning tree)
45. MSTs in Practice
(Real-world applications)
46. Quiz: Unique MST with Unique Weights
Knowledge check
47. Quiz: Kruskal vs Prim on Dense Graphs
Knowledge check
48. Section Recap
(What you learned)