最小生成树总结

Here_SDUT

发布于 2022-06-29 15:13:49

1.2K0

发布于 2022-06-29 15:13:49

一、定义

给定一张带权无向图 G=（V，E），n = |V|， m = |E|。由 V 中全部 n 个顶点和 E 中 n-1 条边构成的无向连通子图被称为 G 的一棵生成树。边权和最小的生成树被称为无向图 G 的最小生成树（Minimum Spanning Tree,MST）。

二、定理&推论

1.任意一棵最小生成树一定包含无向图中权值最小的边。证：反证法。假设无向图存在一棵不包含权值最小边的最小生成树。若把这条权值最小边插入到树中，会形成一个环，且环上的其他每条边的权值都比这条插入的边大，因此，用这条插入的边替换环中任意一条边都能得到更小的生成树，与假设矛盾。 2.推论：给定一张带权无向图 G=（V，E），n = |V|， m = |E|。从 E 中选出 k< n-1G 的一个生成森林。若再从剩下的 m-k 条边中选 n-1-k 条添加到生成森林中，使其成为 G 的生成树，并且保证后选的边权值之和最小，则该生成树一定包含这 m-k 条边中连接生成森林的两个不连通节点的权值最小的边。

暂时不太知道怎么应用这两个结论证明下文的两个算法，这里仅做介绍

三、Kruskal算法

Kruskal总是维护无向图的最小生成森林。最初，可以认为生成森林由零条边组成，每个节点各自构成一棵仅包含一个点的树。
任意时刻，Kruskal从剩余的边中选出一条权值最小的边，并且这条边的两个端点属于生成森林中两棵不同的树（不连通），把该边加入生成森林。图中节点属于那棵树可以用并查集维护。
具体流程：建立并查集，每个点各自为一个集合。每条边按照权值从小到大排序，遍历每条边(x,y,z)。若x,y属于同个集合，则忽略这条边，扫描下一个边。否则，合并x,y所在的集合，并把z加到答案中。扫描完所有边后，第4步中所加的边构成最小生成树。时间复杂度为O(mlogm)。
算法证明：要证明Kruskal算法生成的是最小生成树，我们分两步来证明：（1）Kruskal算法一定能得到一个生成树；（2）该生成树具有最小代价。证明如下：（1）假设该算法得到的不是生成树（有环或不连通），由于算法要求每次加入边的两端点属于两个不同的集合及不会形成环，所以第一种情形不存在。又由于存在最小生成树的前提是图为连通图，故第二种情况也不存在。（2）假设图有n个顶点，则生成树一定具有n-1条边。假设该图的最小生成树为M。先做出如下假设： 1)Kruskal得到的树为K。 2)K 和 M 中不同的边的条数为m,其它n-1-m条边相同，这n-1-m条边构成边集 E 。 3)在K中而不在M中的边按代价从小到大依次为a_1，a_2，…，a_m。 4)在U中而不在T中的边按代价从小到大依次为x_1，x_2，…，x_m。现在我们通过把 M 转换为 K （把 K 的边依次移入 M 中），来证明 M 和 K 相同。首先，我们将a_1移入 M 中，由于 M 本身是一棵树，此时任意加一条边都构成回路，所以a_1的加入必然产生一条回路，且这条回路必然包括x_1，x_2，…，x_m中的边。（否则a_1与 E 中的边构成回路，而 E 也在 K 中，这与 K 中无回路矛盾）在这个回路中删除属于x_1，x_2，…，x_m且代价最大边x_i构成一个新的生成树 V 。假设 a_1 代价小于 x_i ，则 V 的代价小于 M ，这与 M 是最小代价树矛盾，所以 a_1 不可能小于 x_i 。假设 a_1 大于 x_i，按照Kruskal算法，首先考虑代价小的边，则执行Kruskal算法时，x_i应该是在a_1,a_2,…,a_m之前考虑，所以考虑 x_i 之前，K 中的边只能是 E 中的边，而 x_i 既然没加入树 K ，就说明 x_i 必然与 E 中的某些边构成回路，但x_i和 E 又同时在 M 中，这与M是生成树矛盾，所以a_1也不可能大于x_i。因此，新得到的树 M 与 K 具有相同代价。依次类推，把a_1，a_2，…，a_m的边逐渐加到 M 中，最终得到的树 V 与 M 代价相同。

证必。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5+10;

struct node{
    int u, v, w;
    const bool operator < (const node &t)const {return w < t.w;}
}edge[maxn];

int fa[maxn];
int Find(int x) {
    if(fa[x] == x) return x;
    else return fa[x] = Find(fa[x]);
}

int main(){
    int n, m;
     cin >> n >> m;
     for(int i  = 0;  i< m; i++){
            cin >> edge[i].u >> edge[i].v  >> edge[i].w;
     }
     sort(edge,edge+m);
     for(int i = 1; i <=n; i++){
         fa[i] = i;
     }
     int cnt = 0, ans = 0;//cnt存加入森林的边数，判断是否存在生成树，若边树等于n-1，则存在生成树。
     for(int i = 0;  i< m; i++){
         int x = Find(edge[i].u), y = Find(edge[i].v);
         if(x == y) continue;
         fa[x] = y;
         ans += edge[i].w;
         cnt++;
     }
     if(cnt != n-1) puts("impossible");
     else cout << ans << endl;
}

四、Prim

Prim算法做法有所不同，prim总是维护最小生成树的一部分，最初定义1号节点为最小生成树的初始点。
任意时刻，设已确定属于最小生成树的点集为T,剩余其他节点的集合为S。每次在S中找与集合T距离最小的点x，距离的定义为：节点x与集合T中的节点之间权值最小的边的权值。然后将此点从S中删除，加入到T中，并把此点和集合T的距离加到答案中。
若点x从集合S移动到T，则扫描x的所有边，更新一下另一个端点到集合T的距离。
具体流程：维护一个数组d：若x∈S，则d[x]表示节点x到集合T的距离。若x∈T，则d[x]就等于x被加入到T时选出的最小边的权值。用一个sta数组标记节点是否属于T。每次从未被标记的节点中选取d值最小的，把它标记（加入T中），同时扫描所有出边，更新另一个端点的d值。最后，最小生成树的权值总和为\sum_{x=2}^{n}d[x]
时间复杂度 O(n^2)，用优先队列可以优化到O(mlogn),prim主要用于稠密图，尤其是完全图的最小生成树求解。

prim无优化版本

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e3 + 10;
int mp[maxn][maxn], d[maxn], n, m;
bool sta[maxn];

int prim() {
    memset(d, 0x3f, sizeof(d));//d数组初始化为无穷大
    int res = 0;//记录最小生成树的总权值和
    for (int i = 0; i < n; i++) {//这里i从0开始，第一次循环找到的最小点为1号点（相当于S集合的初始化）
        int x = 0;
        for (int j = 1; j <= n; j++)//寻找S集合中距离T最近的点
            if (!sta[j] && (x == 0 || d[x] > d[j])) x = j;
        if (i && d[x] == 0x3f3f3f3f) return 0x3f3f3f3f;//如果找到的最小点与S集合无边（这里显示为无穷大），则没有最小生成树，直接返回无穷大。
        sta[x] = 1;//点入S集合
        for (int j = 1; j <= n; j++) {//遍历入S集合的点的所有边，更新另一端点到S的距离
            if (!sta[j]) d[j] = min(d[j], mp[j][x]);
        }
        if (i) res += d[x];//第一次循环找的是1号点，不用加边权
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(mp, 0x3f, sizeof mp);
    for (int i = 1; i <= n; i++) mp[i][i] = 0;//记得初始化
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = mp[v][u] = min(mp[u][v], w);//如果有重边则这样处理
    }
    int ans = prim();
    if (ans == 0x3f3f3f3f)//返回无穷大说明无最小生成树，输出impossible
        puts("impossible");
    else
        cout << ans << endl;
}

优先队列优化

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e3 + 10;
int mp[maxn][maxn], d[maxn], n, m;
bool sta[maxn];
int cnt;
int prim() {
    memset(d, 0x3f, sizeof(d));
    int res = 0;
    d[1] = 0;
    priority_queue<pair<int, int>> q;
    q.push({0, 1});
    while (cnt < n && q.size()) {//循环条件与朴素做法有些不同，第一个条件代表最小生成树的条件，第二个条件判断队列是否为空
        auto now = q.top();
        q.pop();
        int x = now.second;
        if (sta[x]) continue;//如果属于S集合则不操作
        res += -now.first;
        sta[x] = 1;
        cnt++;
        for (int j = 1; j <= n; j++) {
            if (!sta[j] && d[j] > mp[j][x]) {
                d[j] = mp[j][x];
                q.push({-d[j], j});//把更新过的值压入队列待匹配，这里取负号是因为我们要取最小值，而优先队列默认输出最大值
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(mp, 0x3f, sizeof mp);
    for (int i = 1; i <= n; i++) mp[i][i] = 0;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = mp[v][u] = min(mp[u][v], w);
    }
    int ans = prim();
    if (cnt != n)//集合中没有n个点说明不存在最小生成树
        puts("impossible");
    else
        cout << ans << endl;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-1-07 1，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度