Minimum spanning tree
Connect every node of an undirected weighted graph with the least total edge weight. Two greedy strategies get there — and provably reach the same optimum:
- Kruskal sorts all edges once, then takes each lightest edge unless it would close a cycle.
- Prim grows one tree from a start node, always adding the lightest edge that leaves it.
Both implementations share a LinkedList trick as their union-find: two endpoints are in the same component exactly when their LinkedListNode.List is the same list; merging clusters is splicing one list into the other.
var ug = new AdjacencyList<string, int>();
ug.AddUndirectedEdge("A", "B", 4);
ug.AddUndirectedEdge("A", "C", 1);
ug.AddUndirectedEdge("B", "C", 3);
ug.AddUndirectedEdge("B", "D", 2);
ug.AddUndirectedEdge("C", "D", 5);
// Kruskal — static, one call
var mstKruskal = MinimumSpanningTree.CalculateByKruskal<string, int>(ug);
// Prim — instance, grown from the first node
var prim = new PrimAlgorithm<string, int>(ug);
var mstPrim = prim.GetMinimumSpanningTree();
Both return the MST as an undirected AdjacencyList (each tree edge stored in both directions). For the sample graph above the MST is {A–C, B–D, B–C} with total weight 6.