一.最小生成树之 p r i m prim prim算法

Prim算法适用于稠密图 Kruskal适用于稀疏图

M S T MST MST M i n i m u m S p a n n i n g T r e e Minimum Spanning Tree MinimumSpanningTree,最小生成树)问题有两种通用的解法, P r i m Prim Prim算法就是其中之一,它是从点的方面考虑构建一颗 M S T MST MST,大致思想是:设图 G G G顶点集合为 U U U,首先任意选择图G中的一点作为起始点a,将该点加入集合 V V V,再从集合 U V U-V UV中找到另一点b使得点 b b b V V V中任意一点的权值最小,此时将b点也加入集合 V V V;以此类推,现在的集合V={a,b},再从集合 U V U-V UV中找到另一点c使得点c到V中任意一点的权值最小,此时将c点加入集合V,直至所有顶点全部被加入 V V V,此时就构建出了一颗 M S T MST MST。因为有N个顶点,所以该 M S T MST MST就有 N 1 N-1 N1条边,每一次向集合 V V V中加入一个点,就意味着找到一条 M S T MST MST的边。
p r i m prim prim算法图文详解链接
用代码照着上面链接的图推一遍,很清晰的,只不过图中的mst[i]=0在代码里体现的是-1,以及新起点(mst[i]=-1)是不会再更新的。
O ( n 2 ) O(n^2) O(n2)

p r i m prim prim完整代码(计算最短距离并输出路径)

输入

7 9
1 2 28
1 6 10
2 3 16
2 7 14
3 4 12
4 5 22
4 7 18
5 6 25
5 7 24

输出

1 6 10
6 5 25
5 4 22
4 3 12
3 2 16
2 7 14
weight of mst is 99

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cerr<<"# "<<x<<endl
const ll N=2e3;
const ll base=137;
const ll mod=2147483647;
const ll INF=1<<30;
ll mp[N][N];
ll n,m,x;
ll lowcost[N],mst[N];
void prim(ll u)//最小生成树起点
{
    ll sum_mst=0;//最小生成树权值
    for(int i=1;i<=n;++i)
    {
        //初始化从当前的起点(起点会变)到i的距离(权值)
        lowcost[i]=mp[u][i];
        mst[i]=u;
    }
    mst[u]=-1;//等于-1就意味着已经放到了mst集合里了
    for(int i=1;i<n;++i)//n-1条边,迭代n-1次就好
    {
        ll minn=INF;
        ll v=-1;//flag
        //在lowcost数组中寻找还未加入mst的最小值
        for(int j=1;j<=n;++j)
        {
            if(mst[j]!=-1&&lowcost[j]<minn)
            {//需要更新就更新
                v=j;
                minn=lowcost[j];
            }
        }
        if(v!=-1)//如果找到了最小边
        {
            //输出路径(起点,终点,距离)
            printf("%lld %lld %lld\n",mst[v],v,lowcost[v]);
            //标记一下,已经找到了,这个点已经不能走人了
            mst[v]=-1;
            sum_mst+=lowcost[v];
            for(int j=1;j<=n;++j)
            {
                if(mst[j]!=-1&&lowcost[j]>mp[v][j])
                {
                    lowcost[j]=mp[v][j];
                    mst[j]=v;
                }
            }
        }
    }
    printf("weight of mst is %lld\n",sum_mst);
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=m;++i)
    {
        ll u,v,w;
        scanf("%lld %lld %lld",&u,&v,&w);
        if(mp[u][v])mp[u][v]=mp[v][u]=min(w,mp[u][v]);//判断重边
        else mp[u][v]=mp[v][u]=w;//邻接矩阵存无向图
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i==j)mp[i][j]=0;
            else if(!mp[i][j])mp[i][j]=INF;
        }
    }
    prim(1);
    return 0;

}

堆优化版本

时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
具体代码见文末的例题

二.最小生成树之 k r u s k a l kruskal kruskal算法

K r u s k a l Kruskal Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列,接着按照顺序选取每条边,如果这条边的两个端点不属于同一集合,那么就将它们合并,直到所有的点都属于同一个集合为止。至于怎么合并到一个集合,那么这里我们就可以用到一个工具——-并查集换而言之, K r u s k a l Kruskal Kruskal算法就是基于并查集的贪心算法。
时间复杂度
O ( n l o g n ) O(|n|log|n|) O(nlogn)
k r u s k a l kruskal kruskal算法图文详解链接

k r u s k a l kruskal kruskal完整代码(计算最短距离并输出路径)

输入:

7 9
1 2 28
1 6 10
2 3 16
2 7 14
3 4 12
4 5 22
4 7 18
5 6 25
5 7 24

输出:

1 6 10
3 4 12
2 7 14
2 3 16
4 5 22
5 6 25
weight of mst is 99

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,ll>pdl;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cerr<<"# "<<x<<endl
const ll N=10005;
const ll base=137;
const ll mod=2147483647;
const double INF=double(0x7f7f7f7f*1.0);
//const double INF=double(INT_MAX*1.0);
ll t,n,m,x;
struct edge
{
    ll u,v,w;
    bool operator<(const edge& a)const
    {
        return w<a.w;
    }
}a[N];
ll par[N],high[N];

inline void init(ll n)
{
    for(int i=0;i<n;++i)
    {
        par[i]=i;
        high[i]=0;
    }
}
//查
//查询树的根
inline ll Find(ll x)
{
    return par[x]==x?x:par[x]=Find(par[x]);
}
//并
inline void unite(ll x,ll y)
{
    x=Find(x);
    y=Find(y);
    if(x==y)return ;
    //谁高谁是爸爸
    if(high[x]<high[y])
        par[x]=y;
    else {
        par[y]=x;
        if(high[x]==high[y])
            high[x]++;
    }
}
//判
inline bool check(ll x,ll y)
{
    return Find(x)==Find(y);
}
inline kruskal(ll n,ll m)//点数n,边数m
{
    ll sum_mst=0;//mst权值
    ll num=0;//已选择边的边数
    sort(a,a+m);
    init(n);
    for(int i=0;i<m;++i)
    {
        ll u=a[i].u;
        ll v=a[i].v;
        if(Find(u-1)!=Find(v-1))//注意图最开始的下标是1,并查集是0
        {
            printf("%lld %lld %lld\n",u,v,a[i].w);
            sum_mst+=a[i].w;
            num++;
            unite(u-1,v-1);
        }
        if(num>=n-1)break;
    }
    printf("weight of mst is %lld\n",sum_mst);
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=0;i<m;++i)
    {
        scanf("%lld %lld %lld",&a[i].u,&a[i].v,&a[i].w);
    }
    kruskal(n,m);
    return 0;
}

三. p r i m prim prim k r u s k a l kruskal kruskal相对比

1. 1. 1.时间上

P r i m Prim Prim 适合稠密图,复杂度为 O ( n 2 ) O(n^2) O(n2)
),因此通常使用邻接矩阵储存;但是堆优化为 O ( n l o g n ) O(nlogn) O(nlogn)

稠密图 P r i m Prim Prim 优于 K r u s k a l Kruskal Kruskal,稀疏图 K r u s k a l Kruskal Kruskal 优于 P r i m Prim Prim

2. 2. 2.空间上

P r i m Prim Prim 适合点少边多, K r u s k a l Kruskal Kruskal 适合边多点少。

注意:堆优化的 Prim 用空间换时间,空间要求更高。

3. 3. 3.USACO07DEC道路建设 B u i l d i n g R o a d s Building Roads BuildingRoads p r i m prim prim算法+堆优化与 K r u s k a l Kruskal Kruskal+路径压缩对比)

USACO07DEC道路建设Building Roads( p r i m prim prim算法+堆优化与 K r u s k a l Kruskal Kruskal+路径压缩对比)

可以看到下图两种方法比较:
p r i m prim prim

K r u s k a l Kruskal Kruskal:

答案详解链接