图 - 最小生成树

· · 算法·理论

<目录

最小生成树 \sf\color{grey}Minimum\ Spanning\ Tree

生成树，是指在一张无向图中去掉一些边后剩下的子树。
最小生成树，就是图里边权和最小的生成树。

如何求最小生成树呢？
我们还是从点和边入手。

先从边开始吧……

\textsf{Kruskal}

\sf\tiny\color{#EEEEEE}克鲁斯卡尔

他既然要边权和最小，那我把边按照边权排序，从小到大加到树里面不就行啦？
慢着！
如果组成了环该怎么办？
看来，已经在生成树中的两个点不能再有新的边相连了。
怎么知道这两个点已经在生成树中了呢？

如果我把在树中的点归为一个集合，那么添一条边就相当与加一个点到集……
怎么那么耳熟……
哦！
是并查集！
添一条边，就合并两个点的集合。如果这条边连接的两个点已经在同一棵树中，说明这条边不合法！

那……什么时候停下来呢？
树的边数等于树的点数减一，说明如果我已经添加了点数减一条合法的边的话，那么算法就结束了。

思路理清后，让我们来写……

代码

#include<cstdio>
#include<algorithm>
#define INF 0x3fffffff
#define Min(a,b) ((a)<(b)?(a):(b))
struct L{int F,T,W;}E[400010];
bool Compare(L a,L b){return a.W<b.W;}
int Fa[5005],N,M,T,Ans;
int Find(int n)
{
    if(Fa[n]!=n)    Fa[n]=Find(Fa[n]);
    return Fa[n];
}
void Merge(int a,int b)
{
    a=Find(a),b=Find(b);
    Fa[b]=a;
}
bool Judge(int a,int b)
{
    a=Find(a),b=Find(b);
    return (a==b);
}
int main()
{
    scanf("%d%d",&N,&M);M*=2;
    for(int i=1;i<=N;i++)   Fa[i]=i;
    int ou,ov,ow;
    for(int i=0;i<M;i++)
        scanf("%d%d%d",&ou,&ov,&ow),
        E[i].F=ou,E[i].T=ov,E[i].W=ow,i++,
        E[i].F=ov,E[i].T=ou,E[i].W=ow;
    std::sort(E,E+M,Compare);
    for(int i=0;i<M;i++)
    {
        if(!Judge(E[i].F,E[i].T))
            Merge(E[i].F,E[i].T),Ans+=E[i].W,T++;
        if(T==N-1)  break;
    }
    if(T!=N-1)
    {
        printf("orz");
        return 0;
    }
    printf("%d",Ans);
    return 0;
}

除了边，我们还有另一个突破口：
点。

\textsf{Prim}

我们一开始随便确定一个点作为起点，然后一个一个往里边加点就好。
如何保证最小？
只需要找最小的，连接了树里的点的边，然后加入这条变和连接的另外一个点。

找最小？
于是我们又请出了我们的二叉堆。

确定一个点后，把他所连接的所有边扔进小根堆里。
然后一个一个边来找边权最小的边，找到下一个点，然后在把他所有的边都扔进堆里……

直到所有的点加入树中。

注意如果一条变连的另一个点已经加入了树，那这条变是非法的，要舍弃。

自己亲手写了一下……

代码

#include<cstdio>
#include<queue>
using std::vector;
using std::priority_queue;
struct Edge
{
    int To,Dis;
    bool operator<(Edge m)const
    {
        if(Dis==m.Dis)
            return To>m.To;
        else return Dis>m.Dis;
    }
};
vector<Edge> Graph[5050];
priority_queue<Edge> Search;
int N,M,o1,o2,o3,Edges,Fans;
bool InTree[5050];
void PushPoint(int n)
{
    InTree[n]=true;
    const int ol=Graph[n].size();
    for(int i=0;i<ol;i++)
        Search.push(Graph[n][i]);
    return;
}
int main()
{
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++)
        scanf("%d %d %d",&o1,&o2,&o3),
        Graph[o1].push_back({o2,o3}),
        Graph[o2].push_back({o1,o3});
    PushPoint(1);
    while(!Search.empty())
    {
        const Edge S=Search.top();
        Search.pop();
        if(!InTree[S.To])
            Edges++,Fans+=S.Dis,
            PushPoint(S.To);
    }
    if(Edges>=N-1)  printf("%d",Fans);
    else            printf("orz");
    return 0;
}

来对比一下

算法名 \textsf{Kruskal} \textsf{Prim}
图解
时间复杂度 \sf O(m\log m) \sf O((n+m)\log n)
算法资瓷 并查集 二叉堆（Fib堆？）

暴力 Prim 的复杂度比 Kruskal 优，但 不一定 实际跑得更快。

完结散花