最小生成木は、無向重み付きグラフにおいて、すべてのノードをつなぐことを保証しつつ、選ばれた辺の総和が最小となる構造である。この構造には複数の可能性があり、その中でも総和が最小のものを最小生成木と呼ぶ。n個のノードを持つグラフでは、最小生成木は必ずn-1本の辺で構成される。また、最小生成木にはサイクルが存在しない。

Kruskalアルゴリズムは、最小生成木を求めるための貪欲アルゴリズムであり、以下のような手順に従う。

1. すべての辺を重みの小さい順にソートする。
2. 現在の辺を追加してもサイクルを形成しない場合、それを選択し、並列集合（Union-Find）に追加する。
3. サイクルを形成する場合は、その辺をスキップする。
4. すべての辺を検討した後、最小生成木が完成する。

以下は、KruskalアルゴリズムのJava実装例である。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

    public static int MAXN = 5001;
    public static int MAXM = 200001;
    public static int[] father = new int[MAXN];
    public static int[][] edges = new int[MAXM][3];
    public static int n, m;

    public static void build() {
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
    }

    public static int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    public static boolean union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            build();
            for (int i = 0; i < m; i++) {
                in.nextToken();
                edges[i][0] = (int) in.nval;
                in.nextToken();
                edges[i][1] = (int) in.nval;
                in.nextToken();
                edges[i][2] = (int) in.nval;
            }
            Arrays.sort(edges, 0, m, (a, b) -> a[2] - b[2]);
            int ans = 0;
            int edgeCnt = 0;
            for (int[] edge : edges) {
                if (union(edge[0], edge[1])) {
                    edgeCnt++;
                    ans += edge[2];
                }
            }
            out.println(edgeCnt == n - 1 ? ans : "orz");
        }
        out.flush();
        out.close();
        br.close();
    }
}

Primアルゴリズムは、最小生成木を求める別のアプローチであり、以下のような手順に従う。

1. 開かれたノードの集合をset、開かれた辺の集合を小根ヒープ（heap）として扱う。
2. 任意のノードから開始し、そのノードをsetに追加し、そのノードに関連するすべての辺をheapに追加する。
3. heapから最小の重みを持つ辺を取り出し、その先のノードがsetに含まれていない場合、その辺を最小生成木に追加し、そのノードをsetに追加し、そのノードに関連するすべての辺をheapに追加する。
4. heapが空になるまで繰り返す。

以下は、PrimアルゴリズムのC++実装例である。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<vector<int>>> graph;

void build(int n) {
    for (int i = 0; i <= n; i++)
        graph.push_back(vector<vector<int>>());
}

int main() {
    int n, m;
    cin >> n >> m;
    build(n);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({ b, c });
        graph[b].push_back({ a, c });
    }

    auto cmp = [](vector<int> a, vector<int> b) { return a[1] > b[1]; };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> heap(cmp);

    for (auto edge : graph[1]) {
        heap.push(edge);
    }

    vector<bool> visited(n + 1, false);
    visited[1] = true;
    int ans = 0;
    int count = 1;

    while (!heap.empty()) {
        vector<int> current = heap.top();
        heap.pop();
        int node = current[0];
        int weight = current[1];

        if (!visited[node]) {
            count++;
            ans += weight;
            visited[node] = true;
            for (auto neighbor : graph[node])
                heap.push(neighbor);
        }
    }

    if (count == n)
        cout << ans;
    else
        cout << "orz";

    return 0;
}

最小生成木の他の応用例として、村と井戸のコスト計算や、特定の条件を満たすパスの存在確認などが挙げられる。

最小ボトルネック木は、グラフが接続されていることを保証しつつ、最大の辺の重みが最小となる生成木である。最小生成木は常に最小ボトルネック木であるが、逆は必ずしも成り立たない。

以上のように、最小生成木は様々なアルゴリズムを通じて実装可能であり、さまざまな応用がある。