查看“︁11-图论/02-最小生成树”︁的源代码


== 最小生成树（MST） ==

在一张带权无向连通图中，生成树是包含所有 <math>n</math> 个顶点且只有 <math>n - 1</math> 条边的连通子图。'''权值和最小的生成树'''即为最小生成树。

== Kruskal 算法 ==

对边按权值排序，用并查集维护连通性，从小到大依次加入不构成环的边。

=== 模板 ===

<syntaxhighlight lang="cpp">
struct Edge
{
    int u, v, w;
    bool operator<(const Edge& that) const
    {
        return w < that.w;
    }
};

// 并查集部分见并查集页面
int fa[MAXN];

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int kruskal(vector<Edge>& edges, int n)
{
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++) fa[i] = i;

    int mst = 0, cnt = 0;
    for (auto [u, v, w] : edges)
    {
        int fu = find(u), fv = find(v);
        if (fu != fv)
        {
            fa[fu] = fv;
            mst += w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return mst; // 若 cnt < n - 1 则图不连通
}
</syntaxhighlight>

时间复杂度：<math>O(m\log m)</math>（排序），适合稀疏图。

== Prim 算法 ==

从任意点出发，每次选择与当前生成树距离最近的点加入。

=== 模板 ===

<syntaxhighlight lang="cpp">
int prim(vector<pair<int, int>> g[], int n)
{
    vector<bool> vis(n + 1, false);
    vector<int> dis(n + 1, 0x3f3f3f3f);
    dis[1] = 0;
    int mst = 0;

    for (int i = 1; i <= n; i++)
    {
        int u = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == 0 || dis[j] < dis[u]))
                u = j;
        if (dis[u] == 0x3f3f3f3f) return -1; // 不连通
        vis[u] = true;
        mst += dis[u];
        for (auto [v, w] : g[u])
            if (!vis[v])
                dis[v] = min(dis[v], w);
    }
    return mst;
}
</syntaxhighlight>

时间复杂度：<math>O(n^2)</math>，适合稠密图。可用优先队列优化至 <math>O(m\log n)</math>。

[[Category:图论]]
[[Category:三三文档]]