Minimum Spanning Trees
Ever wondered how engineers decide the cheapest way to connect multiple cities with roads? Minimum spanning trees (MST) solve exactly this problem by finding the lowest-cost way to connect all vertices in a graph.
Kruskal's algorithm works like a bargain hunter - it sorts all edges by weight and picks the cheapest ones first. Start by listing all edges from smallest to largest weight, then keep adding the cheapest edge that doesn't create a cycle. You'll stop when all vertices are connected, guaranteed to have the minimum total cost.
Prim's algorithm takes a different approach by growing the tree from a single starting point. Pick any vertex to begin, then repeatedly add the cheapest edge that connects your existing tree to a new vertex. This method feels more natural since you're building outward step by step.
Top Tip: Kruskal's focuses on edges globally, whilst Prim's grows locally from your current tree - both give the same minimum weight!
