Minimum Spanning Tree

Kruskal's & Prim's Algorithms

1:00

How to find the cheapest set of edges that connects every vertex in a weighted graph, using Kruskal's and Prim's greedy algorithms.

By the end, you can

Define a spanning tree and state how many edges it has for a graph of V vertices.
Run Kruskal's algorithm on a small graph, identifying accepted and rejected edges in sorted order.
Explain what Union-Find does and why Find(u) == Find(v) means an edge would form a cycle.
Run Prim's algorithm from a given start vertex, tracking the priority-queue frontier at each step.
State the cut property and explain why it guarantees the greedy choice is always correct.
Compare Kruskal and Prim by time complexity and identify which suits sparse vs dense graphs.
Distinguish the MST problem from the single-source shortest-path problem.
Describe at least two real-world applications of minimum spanning trees.

Up next in Algorithms & Graph Algorithms