11-图论/02-最小生成树

最小生成树（MST）

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

Kruskal 算法

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

模板

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 则图不连通
}

时间复杂度：[math]\displaystyle{ O(m\log m) }[/math]（排序），适合稀疏图。

Prim 算法

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

模板

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;
}

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