最小生成树

2024-02-07

算法>图论

6.4k 词

0 前言

总结一些最小生成树问题的常用模板

1 Kruskal

一种简单易实现的算法，基于贪心和并查集

1.1 原理

将所有的边按照边权从小到大排序，依次遍历每条边，如果两点未联通，就在生成树中加上这条边，选取 $n-1$ 条边即可连成最小生成树

1.2 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;
const int M = 2e5 + 5;

int n, m;

struct Edge{
    int u, v, w;
    friend bool operator < (const Edge & x, const Edge & y) {
        return x.w < y.w;
    }
} E[M];

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

inline pair<int, bool> Kruskal(int n, int m) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    sort(E + 1, E + m + 1);
    int res = 0, cnt = 1;
    for (int i = 1; i <= m; i++) {
        int fu = Find(E[i].u), fv = Find(E[i].v);
        if (fu ^ fv) {
            fa[fu] = fv;
            res += E[i].w;
            cnt++;
        }
    }
    return make_pair(res, cnt == n);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
    }
    auto res = Kruskal(n, m);
    if (res.second) {
        printf("%d\n", res.first);
    } else {
        puts("orz");
    }
    return 0;
}

2 Prim

另一种基于贪心和堆/优先队列的算法，类似于 $Dijkstra$

2.1 原理

将所有的点分为两个集合:已经在最小生成树中和还未在最小生成树中，每次挑选两边分别连接两个集合中的点的权值最小的边，将不在最小生成树的一端加入到最小生成树中。

未经过堆优化的Prim算法在稠密图中表现良好，

2.2 代码实现

未优化版

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;

vector<pair<int, int>> E[N];

int dis[N];
bool vis[N];

inline pair<int, bool> Prim(int n)
{
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    int cnt = 0, res = 0;
    while (true)
    {
        int u = 0;
        for (int v = 1; v <= n; v++)
            if (!vis[v] && dis[v] < dis[u])
                u = v;
        if (u == 0)
            break;
        cnt++;
        res += dis[u];
        vis[u] = true;
        for (auto nxt : E[u])
        {
            int v = nxt.first, w = nxt.second;
            if (dis[v] > w)
                dis[v] = w;
        }
    }
    return make_pair(res, cnt == n);
}

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        E[x].push_back(make_pair(y, z));
        E[y].push_back(make_pair(x, z));
    }
    auto res = Prim(n);
    if (res.second)
        printf("%d\n", res.first);
    else
        puts("orz");
    return 0;
}

优先队列优化版

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;

vector<pair<int, int>> E[N];

int dis[N];
bool vis[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;

inline pair<int, bool> Prim(int n)
{
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    int cnt = 0, res = 0;
    Q.push(make_pair(0, 1));
    while (!Q.empty() && cnt < n)
    {
        int u = Q.top().second, d = Q.top().first;
        Q.pop();
        if (vis[u])
            continue;
        cnt++;
        res += d;
        vis[u] = true;
        for (auto nxt : E[u])
        {
            int v = nxt.first, w = nxt.second;
            if (dis[v] > w)
            {
                dis[v] = w;
                Q.push(make_pair(dis[v], v));
            }
        }
    }
    return make_pair(res, cnt == n);
}

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        E[x].push_back(make_pair(y, z));
        E[y].push_back(make_pair(x, z));
    }
    auto res = Prim(n);
    if (res.second)
        printf("%d\n", res.first);
    else
        puts("orz");
    return 0;
}

3 应用

次小生成树

Luogu P4180 [BJWC2010] 严格次小生成树

先求出最小生成树，每次考虑添加还未使用过的边，并将原树上两点路径上的最长边删去，获得次小生成树

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int M = 3e5 + 5;

vector<pair<int, int>> G[N];

struct Edge
{
    int u, v, w;
    bool tag;
} E[M];

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

int n, m;

long long ans0;

inline long long kruskal()
{
    long long mst = 0;
    sort(E + 1, E + m + 1, [&](Edge A, Edge B)
         { return A.w < B.w; });
    for (int i = 1; i <= m; i++)
    {
        int u = find(E[i].u), v = find(E[i].v);
        if (u == v)
            continue;
        mst += E[i].w;
        fa[v] = u;
        G[E[i].u].push_back(make_pair(E[i].v, E[i].w));
        G[E[i].v].push_back(make_pair(E[i].u, E[i].w));
        E[i].tag = true;
    }
    return mst;
}

int f[N][20], dep[N], yist[N][20], ernd[N][20];
void dfs(int u)
{
    dep[u] = dep[f[u][0]] + 1;
    for (int i = 1; i < 20; i++)
    {
        f[u][i] = f[f[u][i - 1]][i - 1];
        if (yist[u][i - 1] == yist[f[u][i - 1]][i - 1])
        {
            yist[u][i] = yist[u][i - 1];
            ernd[u][i] = max(ernd[u][i - 1], ernd[f[u][i - 1]][i - 1]);
        }
        if (yist[u][i - 1] > yist[f[u][i - 1]][i - 1])
        {
            yist[u][i] = yist[u][i - 1];
            ernd[u][i] = max(ernd[u][i - 1], yist[f[u][i - 1]][i - 1]);
        }
        if (yist[u][i - 1] < yist[f[u][i - 1]][i - 1])
        {
            yist[u][i] = yist[f[u][i - 1]][i - 1];
            ernd[u][i] = max(yist[u][i - 1], ernd[f[u][i - 1]][i - 1]);
        }
    }
    for (auto nxt : G[u])
    {
        int v = nxt.first, w = nxt.second;
        if (v == f[u][0])
            continue;
        f[v][0] = u;
        yist[v][0] = w;
        dfs(v);
    }
}

inline int LCA(int u, int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    for (int i = 19; i >= 0; i--)
        if (dep[f[u][i]] >= dep[v])
            u = f[u][i];
    if (u == v)
        return u;
    for (int i = 19; i >= 0; i--)
        if (f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];
    return f[u][0];
}

long long calc(int u, int v, int w)
{
    int l = LCA(u, v);
    int yist_e = 0, ernd_e = 0;
    for (int i = 19; i >= 0; i--)
    {
        if (dep[f[u][i]] >= dep[l])
        {
            if (yist_e == yist[u][i])
                ernd_e = max(ernd_e, ernd[u][i]);
            if (yist_e > yist[u][i])
                ernd_e = max(ernd_e, yist[u][i]);
            if (yist_e < yist[u][i])
            {
                ernd_e = max(yist_e, ernd[u][i]);
                yist_e = yist[u][i];
            }
            u = f[u][i];
        }
        if (dep[f[v][i]] >= dep[l])
        {
            if (yist_e == yist[v][i])
                ernd_e = max(ernd_e, ernd[v][i]);
            if (yist_e > yist[v][i])
                ernd_e = max(ernd_e, yist[v][i]);
            if (yist_e < yist[v][i])
            {
                ernd_e = max(yist_e, ernd[v][i]);
                yist_e = yist[v][i];
            }
            v = f[v][i];
        }
    }
    if (w != yist_e)
        return ans0 - yist_e + w;
    if (ernd_e)
        return ans0 - ernd_e + w;
    return LLONG_MAX;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
        // 注意自环！！！因为这个卡了一上午
        if (E[i].u == E[i].v)
            m--, i--;
    }
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    ans0 = kruskal();
    dfs(1);
    long long ans = LLONG_MAX;
    for (int i = 1; i <= m; i++)
        if (!E[i].tag)
            ans = min(ans, calc(E[i].u, E[i].v, E[i].w));
    printf("%lld\n", ans);
    return 0;
}

4 总结

算法	Kruskal	Prim	优先队列优化的Prim
空间复杂度	$O(M)$	$O(M)$	$O(M)$
时间复杂度	$O(MlogM)$	$O(N^2+M)$	$O(NlogM)$
适用情况	稀疏图和边关系密切	稠密图和顶点关系密切	稀疏图和边关系密切

分类

标签

归档

最新文章