最小生成树

假设 \(n\) 表示图中点数，\(m\) 表示图中边数。

Prim算法

适用于稠密图，时间复杂度 \(O(n^2)\)。

核心思想：每次挑一条与当前集合相连的最短边。

C++ 代码

// st[i] 表示点i是否在当前生成树集合中
// dist[i] 表示点i到当前集合的最短边的长度
// g[i][j] 表示点i和点j之间边的长度
// 返回值：最小生成树中所有边的总长度
int Prim()
{
    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        dist[i] = INF;
        st[i] = false;
    }
    dist[1] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int id = -1, min_dist = INF;
        // 寻找最短边
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && dist[j] < min_dist)
            {
                id = j;
                min_dist = dist[j];
            }
        st[id] = true;
        res += dist[id];
        // 用新加入的点更新其余点到生成树的最短边
        for (int j = 1; j <= n; j ++ )
            if (!st[j])
                dist[j] = min(dist[j], g[id][j]);
    }
    return res;
}

Kruskal算法

适用于稀疏图，时间复杂度 \(O(mlogm)\)。

核心思想：从小到大挑不多余的边。

C++ 代码

// 边的信息
struct Edge
{
    int a, b, v;
    bool operator< (const Edge &W) const
    {
        return v < W.v;
    }
};

// 并查集——寻找当前集合的代表元素
int find(int x)
{
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}

// 所有边存储在 Edge edges[M]; 
// 函数返回最小生成树中所有边的总长度
int Kruskal()
{
    int res = 0;
    // 初始化并查集代表元素
    for (int i = 1; i <= n; i ++ ) father[i] = i;
    sort(edge, edge + m);
    for (int i = 0; i < m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b;
        if (find(a) != find(b))
        {
            res += edge[i].v;
            father[find(a)] = find(b);
        }
    }
    return res;
}