Kruscal最小生成树算法

时间复杂度 O(mlogm)
m表示边

算法主要针对边来展开
边数较少时效率非常高
所以对于稀疏图有很大的优势

依据贪心思想
每次添加最小权值边
且保证不能成环
因为成环一定有浪费的边
通过并查集判断是否成环
若两点已经联通
再次添加连接该两点的边时
会成环

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int fa[N];
int n, m;

//结构体存边
//表示从u到v有一条权值为w的边
struct Edge
{
    int u, v, w;
}edges[N];

//sort的比较函数
bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

//并查集
//寻找祖宗节点
//路径压缩
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int kruskal()
{
    int res = 0;//统计权值和

    int cnt = 0;//统计已联通的点的个数

    for (int i = 1;i <= m;i++)//遍历每一条边
    {
        //取出三个参数 从u到v有一条权值为w的边
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;

        //通过并查集判断
        //如果两点不连通
        //添加边后不会成环
        //则可以添加边
        if (find(u) != find(v))
        {
            fa[find(u)] = find(v);//添加边
            res += w;//该边权值累加
            cnt++;//一个新的点被连入(可以到达)

            //若有n个点
            //最多连接n-1条边 若大于n-1条边 一定成环
            //最少连接n-1条边 不然一定有点不可到达
            //所以恰好连接n-1条边时就是答案
            if (cnt == n - 1)return res;
        }
    }

    //如果cnt最终未达到n-1
    //则无法生成联通树 返回-1
    return -1;
}

int main()
{

    cin >> n >> m;

    //并查集的初始化
    for (int i = 1;i <= n;i++)fa[i] = i;

    //读入边的三个参数
    //分别是 起点 终点 权值
    for (int i = 1;i <= m;i++)
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);

    //对边依照w权值排序
    //排序后从前往后遍历 就是依次取出最小边
    sort(edges + 1, edges + 1 + m, cmp);

    cout << kruskal() << endl;

    return 0;
}

Prim最小生成树算法

时间复杂度 O(mlogn)
m表示边 n表示点

算法主要针对点来展开
算法对于稠密图效率较高
边数非常多的时处理较快

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define x first
#define y second
using namespace std;
const int N = 1010;
int n, m;
int h[N];//类似于dist[N]
bool vis[N];
typedef pair<int, int> PII;

小根堆 q.top()取最小值
第一个参数是该边的权值
第二个参数是到达的点 与数组vector中PII参数顺序不同

//vector<PII>,greater<PII>是小根堆的两个参数
priority_queue<PII, vector<PII>, greater<PII>> q;

//e[i]存了 i作为起点时 i能到达的所有终点(第一参数) 以及对应权值(第二参数)
vector<PII> e[N];

prim算法与堆优化的dijkstra算法有相似之处
两者都用到优先队列
dijkstra算法每次取出离起点最近的点进行松弛操作 标识常为dist
prim算法每次取出离当前的临时生成树最近的点进行松弛操作 标识常为h

int prim()
{
    //求最小值往往要是初始化为正无穷
    memset(h, 0x3f, sizeof h);

    //起点距离设为0 放入堆中
    h[1] = 0;
    q.push(make_pair(h[1], 1));

    int res = 0;//统计边权值

    while (q.size())
    {
        auto tmp = q.top();
        q.pop();

        //如果已经考虑过了 就跳过
        if (vis[tmp.y])continue;

        //要考虑 
        vis[tmp.y] = true;//就标记已经被考虑了
        res += tmp.x;//并且权值累加

        //堆中的第二参数是点的编号
        //遍历能到达的所有终点
        for (auto it : e[tmp.y])
        {
            //取出终点坐标和权值
            //在数组vector中
            //第一参数是点的编号
            //第二参数是权值
            int v = it.x, w = it.y;

            if (vis[v])continue;

            if (h[v] > w)
            {
                h[v] = w;
                //更新所有探索到的边
                //堆中存的是当前的临时生成树中
                //各个点到达的各个边
                //因此 q.top()取出的是
                //到达临时生成树的最小边
                q.push(make_pair(h[v], v));
            }
        }

    }

    return res;
}

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

    int u, v, w;
    while (m--)
    {
        cin >> u >> v >> w;
        e[u].push_back({ v,w });
    }

    cout << prim() << endl;

    return 0;
}

比较Kruskal与Prim

在一片大陆上有很多个国家
Kruskal:许多小国家两两合并
Prim:从一个大国开始延伸吞并周围小国
目标:最终都能实现统一

Kruskal最小生成森林算法

时间复杂度 O(mlogm)
森林==多棵MST
各棵MST之间无法连通

类比Kruskal最小生成树算法
(Prim由点展开 很难求多棵MST)
虽然最终因为图不连通肯定无法走完
但是走多少算多少
中间的部分也是实时正确的

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

using namespace std;

const int N = 110, M = 210;

int n, m;
struct Edge
{
    int a, b, w;
    bool operator< (const Edge &t)const
    {
        return w < t.w;
    }
}e[M];
int p[N];

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

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

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

    sort(e, e + m);

    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b) p[a] = b;
        else res += w;
        //最小生成森林与最小生成树的差别在于
        //没有cnt==n-1的完成判断
        //Kruskal算法做到一半时
        //得到的即是若干独立的最小生成树
    }

    cout << res << endl;

    return 0;
}

Boruvka最小生成森林算法

时间复杂度 O((n+m)logn)
算法展开既考虑点有考虑边

Boruvka是Kruskal和Prim的结合

思想:将更新出的联通块看成一个点
最小边定义:一个联通块 连向其他联通块的所有边中 最小的一条
起初每个点独自成为一个联通块(并查集)

#include<iostream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<pair<int, int>> e[N];
int fa[N], dist[N], p[N];
int n, m;
int res = 0;

//并查集
//路径压缩
int find(int n) 
{
    return fa[n] == n ? n : fa[n] = find(fa[n]);
}

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

    //邻接表存边
    int u, v, w;
    for (int i = 1;i <= m;++i)
    {
        cin >> u >> v >> w;
        e[u].push_back({ v, w });
    }

    //并查集初始化
    for (int i = 1;i <= n;++i) fa[i] = i;

    //Boruvka算法
    while (true)
    {
        bool flag = false;

        //初始化为无穷大
        for (int i = 1;i <= n;++i) dist[i] = INF;

        //遍历所有的边
        for (int i = 1;i <= n;++i)
        {
            for (int j = 0;j < e[i].size();++j)
            {
                int v = e[i][j].x;
                int w = e[i][j].y;

                if (find(i) == find(v)) continue;

                //如果不在一个联通块中
                if (w < dist[find(i)])
                {
                    //更新这个联通块的最小边权值
                    dist[find(i)] = w;
                    //记录最小权值边的终点
                    p[find(i)] = find(v);
                    //联通块的信息都存入了树根节点
                }
            }
        }

        //两层for完成后
        //p数组记录了 当前联通块的 最小边的终点 的编号
        //找所有的联通块
        //遍历所有点(其实有用的是树根节点)
        for (int i = 1;i <= n;++i)
        {
            //如果p指向的块与原块不连通 就把这两个块并集
            //因为我们希望通过最小边连起来
            //若dist[i]==INF 说明原图上不连通 或者不是树根节点
            if (dist[i] < INF && find(i) != find(p[i]))
            {
                flag = true;
                res += dist[i];
                fa[find(i)] = find(p[i]);
            }
        }

        //如果所有联通块都没有最小边 就结束
        if (!flag) break;
    }

    cout << res << endl;

    return 0;
}