Greedy and Minimum Spanning Trees

Minimum spanning trees illustrate a greedy choice certified by a cut, rather than by a vague preference for short edges. Kruskal and Prim use different candidate sets but share the same safe-edge theorem. This lesson focuses on that proof and provides a compact runnable Kruskal example; the existing Graph Algorithms MST lesson remains the main reference for implementation details and related graph prerequisites.

Prerequisites: Existing Minimum spanning tree and Disjoint set union lessons in Graph Algorithms; DSU in Data Structures. Related existing lessons: Minimum spanning tree, Disjoint set union.

Build the idea

1. State the cut property carefully

   A cut partitions vertices into S and its complement. If no edge of the already selected forest crosses the cut, a minimum-weight edge crossing it is safe: some MST containing the current forest also contains that edge. Ties need not put the edge in every MST, only in some optimum consistent with the chosen prefix. Negative weights do not invalidate the property.

2. Correctness proof: exchange on a cycle

   Let an optimum T contain the selected forest. If safe edge e is absent, adding it creates a cycle. The cycle must contain another edge f crossing the same cut. Because the cut respects the selected forest, f is not locked in that forest, and because e is lightest across the cut, weight(e)≤weight(f). Replace f by e; connectivity and acyclicity are restored without increasing cost. The new optimum contains the extended forest.

   $$\mathrm{weight}(T-f+e)\le \mathrm{weight}\left(T\right)$$

3. Recognize Kruskal and Prim invariants

   Kruskal considers edges in global increasing weight order and accepts one only if it joins distinct DSU components. A component cut certifies the accepted edge. Prim grows one connected vertex set and picks a lightest edge leaving that set; its frontier cut certifies the choice. Prim must discard edges whose destination is already inside, and Kruskal must reject cycles. A min-heap or sorting alone does not enforce these conditions.

4. Trace the sample

   Edges 1–2:1,2–3:2,1–3:3,3–4:4,2–4:5 are processed by weight. Accept the first two, reject weight 3 because it closes the 1–2–3 cycle, then accept 3–4. Total is 7. Blindly taking the three smallest edges would cost 6 but leave vertex 4 disconnected, so it would not be a spanning tree at all.

5. Handle forests and existing lesson links

   The program starts with n components and decrements on each successful join. A connected result has count 1 and n−1 accepted edges. Disconnected input yields a minimum spanning forest, with one tree per original component, not a fictitious MST. Self-loops are rejected and parallel edges are allowed. Links in the prerequisite section open the existing graph lesson and DSU content without rewriting them.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
struct DSU{
    std::vector<int>p,size;
    explicit DSU(int n):p(n+1),size(n+1,1){
        std::iota(p.begin(),p.end(),0);
    }
    int find(int x){
        return p[x]==x?x:p[x]=find(p[x]);
    }
    bool join(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return false;
        }
        if(size[a]<size[b]){
            std::swap(a,b);
        }
        p[b]=a;
        size[a]+=size[b];
        return true;
    }
};
struct Edge{
    int u,v,id;
    long long weight;
};
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<Edge>edges(m);
    for(int i=0;i<m;++i){
        std::cin>>edges[i].u>>edges[i].v>>edges[i].weight;
        edges[i].id=i+1;
    }
    std::sort(edges.begin(),edges.end(),[](Edge a,Edge b){
        return a.weight!=b.weight?a.weight<b.weight:a.id<b.id;
    });
    DSU components(n);
    long long total=0;
    int count=n;
    std::vector<int>selected;
    for(Edge e:edges){
        if(components.join(e.u,e.v)){
            total+=e.weight;
            --count;
            selected.push_back(e.id);
        } // Reject cycles; the current forest defines a safe cut.
    }
    std::cout<<count<<' '<<total<<'\n';
    for(int i=0;i<(int)selected.size();++i){
        std::cout<<selected[i]<<(i+1==(int)selected.size()?'\n':' ');
    }
    if(selected.empty()){
        std::cout<<'\n';
    }
}

Complexity analysis

O(m log(m+1)) sorting plus O((n+m) α(n)) DSU work, O(n+m) storage. Forest weight magnitude≤(n−1)·10^9 fits long long. A heap-based Prim version uses an adjacency representation and typically O((n+m) log(n+1)) with an indexed heap, or O(m log(m+1)+n) for a lazy edge heap.

Example input and output

Read n m (1≤n≤100000, 0≤m≤200000), then undirected edges u v weight, vertices 1..n and weights within ±10^9. Print component count and minimum spanning-forest weight, then accepted edge IDs. Count 1 means an MST.

Input

4 5
1 2 1
2 3 2
1 3 3
3 4 4
2 4 5

Output

1 7
1 2 4

The cycle edge of weight 3 is rejected; the weight-4 edge is needed to connect vertex 4.

Practical applications

Use the cut property to recognize safe connectivity choices and justify Kruskal/Prim variants. Return to the existing Graph Algorithms MST lesson for broader implementation practice. Matroids generalize the forest independence behind Kruskal, while Prim exploits additional graph structure.

Check your understanding

What goes wrong with taking the n−1 smallest edges without a cycle check?

Put it into practice

Enumerate every spanning tree of a small weighted graph and compare total weights.