Minimum spanning tree (Prim's)

Grow one tree outward from a start node, always adding the cheapest edge that reaches a new node.

The idea

Keep a frontier of candidate edges leaving the tree built so far. Always take the cheapest one. If it reaches a node already in the tree, it would only create a cycle, so skip it; otherwise the new node joins the tree and its edges become new candidates.

Code

public static List<(char, char, int)> Prim(
        Dictionary<char, List<(char to, int w)>> graph, char start) {
    var inTree = new HashSet<char> { start };
    var pq = new PriorityQueue<(char u, char v, int w), int>();
    foreach (var (v, w) in graph[start]) pq.Enqueue((start, v, w), w);
    var tree = new List<(char, char, int)>();
    while (pq.Count > 0) {
        var (u, v, w) = pq.Dequeue();
        if (inTree.Contains(v)) continue; // both ends already joined, skip
        inTree.Add(v);
        tree.Add((u, v, w));
        foreach (var (x, wx) in graph[v])
            if (!inTree.Contains(x)) pq.Enqueue((v, x, wx), wx);
    }
    return tree;
}

Tips

• Unlike Kruskal, Prim never needs union-find: the "inTree" set alone answers whether a node has already joined.
• Stale queue entries (edges to a node that joined through a cheaper edge) are normal; the "already in tree" check filters them out.

In the .NET library

Prim grows one connected tree outward, while Kruskal picks edges globally by weight regardless of which tree they touch. On the same graph with distinct weights they produce the same tree, just discovered in a different order.