Algorithms on graphs

Kruskal's and Prim's algorithms

A minimum spanning tree (MST) connects every vertex with the least total weight and no cycles; it has $V-1$ edges. Kruskal adds the cheapest remaining edge unless it makes a cycle. Prim grows one tree, always adding the cheapest edge from the tree to a new vertex, and works directly on a distance matrix.