グラフ理論における最小生成木を求める主要なアルゴリズムとして、Prim法とKruskal法がある。n個の頂点とm個の辺を持つグラフを対象とする。

アルゴリズムの特性

Prim法は隣接行列で表現された密グラフに適しており、基本実装の時間計算量はO(n²)である。優先度付きキューを用いてO(n log n)に改善可能である。

Kruskal法は疎グラフに向いており、辺の数mに対してO(m log m)の計算量となる。

アルゴリズムの原理

Prim法の動作

1. 任意の始点から部分木を初期化する
2. 現在の部分木と外部の頂点を結ぶ最小コストの辺を選択
3. 該当する頂点を部分木に追加
4. 新たに追加された頂点からの距離情報を更新
5. 全頂点が含まれるまで2-4を繰り返す

Kruskal法の動作

1. 全ての辺をコストの昇順でソート
2. 最小コストの辺から順に検査
3. 辺が属する2つの頂点が異なる連結成分に属する場合、その辺を採用
4. 採用した辺の2頂点を同一の連結成分に統合
5. n-1本の辺が選択されるまで2-4を繰り返す

実装例：Prim法

#include <iostream>
#include <vector>
#include <climits>

constexpr int MAX_NODES = 105;
int graph[MAX_NODES][MAX_NODES];
int min_distance[MAX_NODES];
bool included[MAX_NODES];

int primAlgorithm(int vertex_count) {
    int total_cost = 0;
    
    for (int i = 1; i <= vertex_count; ++i) {
        min_distance[i] = INT_MAX;
        included[i] = false;
    }
    
    min_distance[1] = 0;
    
    for (int iteration = 0; iteration < vertex_count; ++iteration) {
        int current_vertex = -1;
        
        for (int v = 1; v <= vertex_count; ++v) {
            if (!included[v] && (current_vertex == -1 || 
                min_distance[v] < min_distance[current_vertex])) {
                current_vertex = v;
            }
        }
        
        included[current_vertex] = true;
        total_cost += min_distance[current_vertex];
        
        for (int adjacent = 1; adjacent <= vertex_count; ++adjacent) {
            if (!included[adjacent] && graph[current_vertex][adjacent] < 
                min_distance[adjacent]) {
                min_distance[adjacent] = graph[current_vertex][adjacent];
            }
        }
    }
    
    return total_cost;
}

int main() {
    int n;
    std::cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> graph[i][j];
        }
    }
    
    std::cout << primAlgorithm(n) << std::endl;
    
    return 0;
}

実装例：Kruskal法

#include <iostream>
#include <algorithm>

constexpr int MAX_VERTICES = 105;
constexpr int MAX_EDGES = 10005;

struct GraphEdge {
    int from_vertex;
    int to_vertex;
    int edge_weight;
    
    bool operator<(const GraphEdge& other) const {
        return edge_weight < other.edge_weight;
    }
};

GraphEdge edge_list[MAX_EDGES];
int parent[MAX_VERTICES];

int findRoot(int vertex) {
    if (parent[vertex] != vertex) {
        parent[vertex] = findRoot(parent[vertex]);
    }
    return parent[vertex];
}

int kruskalAlgorithm(int vertex_count, int edge_count) {
    for (int v = 1; v <= vertex_count; ++v) {
        parent[v] = v;
    }
    
    std::sort(edge_list, edge_list + edge_count);
    
    int mst_cost = 0;
    int edges_selected = 0;
    
    for (int i = 0; i < edge_count; ++i) {
        int root_u = findRoot(edge_list[i].from_vertex);
        int root_v = findRoot(edge_list[i].to_vertex);
        
        if (root_u != root_v) {
            parent[root_u] = root_v;
            mst_cost += edge_list[i].edge_weight;
            edges_selected++;
            
            if (edges_selected == vertex_count - 1) {
                break;
            }
        }
    }
    
    return mst_cost;
}

int main() {
    int n;
    std::cin >> n;
    
    int edge_index = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int weight;
            std::cin >> weight;
            edge_list[edge_index++] = {i, j, weight};
        }
    }
    
    std::cout << kruskalAlgorithm(n, n * n) << std::endl;
    
    return 0;
}