最小生成树算法

Prim

原理

  用st数组维护一个集合，最开始为空，每次扩充一个距离当前集合最近的点进入集合，并且更新其他点到集合的最近距离。所有点到集合的初始最近距离为INF，将所有点均加入到集合时算法结束。如果某一次扩充的点到集合的最近距离为正无穷，则说明不存在最小生成树。时间复杂度为O(n^2)。

模板

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int w[N][N];
int dist[N];
bool st[N];
int n, m;

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i) res += dist[t];
        if (i && dist[t] == INF) return INF;

        st[t] = true;

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], w[t][j]);
    }

    return res;
}

int main()
{
    cin >> n >> m;

    memset(w, 0x3f, sizeof w);

    for (int i = 1; i <= n; i ++ ) w[i][i] = 0;

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        w[a][b] = w[b][a] = min(w[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else cout << t << endl;
}

Kruskal

原理

  通过排序得到所有边的序列，从最小的边开始扩展，贪心的思路。维护一个并查集来确定两个点是否属于同一个集合，如果属于同一个集合的两个点还需要增加一条边，则该条边增加后则成环。因此维护一个计数器cnt，当算法结束之后，cnt如果小于n – 1则说明不存在有效的生成树，否则并查集维护的点就是当前生成树。时间复杂度因为用到了排序，因此是mlog(m)。

模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

struct Edge
{
    int a, b, w;
    bool operator < (const Edge& a) const
    {
        return w < a.w;
    }
}edges[M];

int n, m;
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void kruskal()
{
    int res = 0, cnt = 0;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    for (int i = 0; i < m; i ++ )
    {
        auto e = edges[i];
        int a = e.a, b = e.b, w = e.w;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            res += w;
            cnt ++ ;
            p[pa] = pb;
        }
    }

    if (cnt < n - 1) cout << "impossible" << endl;
    else cout << res << endl;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i].a = a, edges[i].b = b, edges[i].w = c;
    }

    sort(edges, edges + m);

    kruskal();

    return 0;
}

例题

AW.859 Kruskal算法求最小生成树（简单）

LC.1489 找到最小生成树中的关键边和伪关键边（困难）