浅谈最小生成树

TimLeo · 2018-08-13 22:52:47 · 个人记录

引言：该文章由kkkac01，Eric_hoo，selina联合出版，感谢“hello luogu”群友对我们的鼓励

~~这几天在看洛谷日报，结果发现竟然没有最小生成树，赶紧过来水一发。~~

最小生成树（Minimum Spanning Tree,MST）

定义：给定一张边带权的无向图 G=(V,E) ,n=|V| ,m=|E|

由V中全部n个顶点和E中n-1条边构成的无向连通子图

被称为G的一颗生成树。

边权之和最小的的生成树被称为无向图G的最小生成树。

实现最小生成树的方法有两种，那么我们就先讨论第一种，也是最常见的一种：

Kruskal算法

首先，我们先来看一个定理：

任意一颗最小生成树一定包含无向图中权值最小的边

证明：

反证法。假设无向图G=(V,E)存在一颗最小生成树不包含权值最小的边。设e=(x,y,z)是无向图中权值最小的边。e添加到树中，会和树上的x到y的路径一起构成一个环，并且环上其它边的权值都比z大。因此，用e代替环上的其它任意一条边，会形成一颗权值和更小的生成树，与假设矛盾。故假设不成立.

是不是感觉看了一堆废话。。。。。。。。。。

好的，进入正题：

Kruskal算法就是建立在这个结论上的

详细的介绍一下Kruskal的算法流程

建立并查集，每个点各自构成一个集合。
把所有的边按照权值从大到小排序，一次扫描每条边(x,y,z)。
若x,y属于同一集合（连通），则忽略。
否则合并xy，并将z累加进答案中。

复杂度O(m log m)

我们图解一下：

让我们把它变成代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int father[100001],n,m,tot,k;

int read(){
    int r=0,f=1;
    char ch;
    do ch=getchar();while(!isdigit(ch) && ch!='-');
    if (ch=='-')f=-1,ch=getchar();
    do r=r*10+ch-48,ch=getchar();while(isdigit(ch));
    return r*f;
}

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

void unionn(int r1,int r2){
    father[find(r2)]=find(r1);
}

struct node{
    int s,e,w;
}edge[200001];

bool operator < (node a,node b){
    return a.w<b.w;
}

void Kruskal(){
    for (int i=1;i<=m;i++)
        if (find(edge[i].s)!=find(edge[i].e)){
            unionn(edge[i].s,edge[i].e);
            tot+=edge[i].w;
            k++;
            if (k==n-1)
                break;
        }
    k==n-1?printf("%d\n",tot):printf("orz\n");
}

int main(){
    n=read();m=read();
    for (int i=1;i<=n;i++)father[i]=i;
    for (int i=1;i<=m;i++){
        edge[i].s=read();
        edge[i].e=read();
        edge[i].w=read();
    }
    sort(edge+1,edge+m+1);
    Kruskal();
    return 0;
}

休息一下，马上回来

好的，接下来我们开始讨论另一个算法：

Prim算法

   Prim算法的思路略有改变。设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。

还是图解吧。。。。。

那么将它变成程序： PS:加了点神奇的优化，思路没变

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int head[10010],to[500010],ww[500010],nxt[500010];
int dis[10010];
bool mark[10010];
int R=0,n,m,ans=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
pair <int,int> pa;

void MEMSET_INF()
{
    for (int i=1;i<=n;++i)
        dis[i]=0x7fffffff;
}

void Prim()
{
    dis[1]=0;
    pa.first=0,pa.second=1,q.push(pa);
    while (!q.empty())
    {
        pair <int,int> p;
        do{
            p=q.top(),q.pop();
        }while (mark[p.second]&&!q.empty());
        if (mark[p.second]&&q.empty()) continue;
        mark[p.second]=1;
        ans+=p.first;
        for (int e=head[p.second];e;e=nxt[e])
            if (ww[e]<dis[to[e]])
                dis[to[e]]=ww[e],q.push(make_pair(dis[to[e]],to[e]));
    }
}

void AddEdge(int u,int v,int w){
    to[++R]=v,ww[R]=w,nxt[R]=head[u],head[u]=R;
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1,u,v,w;i<=m;AddEdge(u,v,w),AddEdge(v,u,w),++i)
        scanf("%d%d%d",&u,&v,&w);
    MEMSET_INF();
    Prim();
    cout << ans << endl;
    return 0;
}

好的，这两个算法今天就介绍到这里，祝大家愉快，也请大佬们不要。。那啥。。，鼓励一下蒟弱。

尾声：这两个算法各有使用之处，Prim适合用于稠密图，Kruskal适用于稀疏图，所以不要一味的去写Kruskal，要按着题目分析，才能真正发挥这两个算法的作用！