4.图论经典算法之最小生成树~Prim

首先介绍一下什么是树：

image.png

可能与本算法有关的性质：两点之间又切仅有一条路！！！

好了，接下来开始讲什么是最小生成树，就是在一个连通图里面在保持连通的性质下进行删边，并且在所有删边后的图里面的边总权值最小的图就是最小生成树，很好理解，假如现在删的还剩n条边，那么一定会有一条多余的边，删掉这个边总权值会进一步减小，所以无论怎么删除，最后结果的都会是一个树，只是得到的这些树的总权值不一样，我们要解决的问题是怎么获得这些树中总权值最小的那个。

关于最小生成树有一些实际应用，其中最典型的是有一些村庄，他们之间可以修互相直达的路，给你任意两个村庄之间修路的代价，问你如何用最小的代价把所有村庄连起来，嘻嘻

介绍一下Prim算法的基本思想：贪心!
没错，又是贪心，prim算法从点出发，首先创建一个空集合，初始化元素全为极大值的数组len用于表示各个点到集合里任意一个点的最小路径值，然后随便选一个点扔进集合，然后用这个点更新和他相连的点的len数组值，然后找出下一个没有进集合但是离集合最近的一个点进入集合，并且用新进入的点更新len值！
是不是有些熟悉啊，有点像什么！对！这不是迪杰斯特拉吗！只不过迪杰斯特拉的len数组存的是到固定点的最小路径，这里存的是到集合的最小值
如果没有理解，没有关系，看图！

image.png

先把C进集合，此时A离集合最短，A进集合，此时lenB为5，lenD为7，lenE为5，选择B或E进入集合，这里选的B，然后F，E，D依次进入集合，所有点都进入集合了，算法结束！
想必大家都看出来了，最小生成树可能不是唯一的，一个图可能拥有不少的最小生成树，但是他们在连通性质和总权值上是等价的哈

下面上代码，没看懂的小可爱或者不知道如何代码实现的看下！其实一直觉得看有注释的代码才最好理解，因为有各种细节，光是讲思路还是太抽象了

void int prim()
{
    memset(len,0x3f,sizeof(len));
    //先把len数组赋值为极大值
    len[u]=0;//到自己的值当然为0
    int now;//接下来要加入集合的点
    int tot=0;//tot用于记录有几个点在集合里
    while(tot<n)//当还没全部进入集合时就要去找下一个点
    {
        int minn=len[0];//把minn置为极大值，len[0]不会被更新因为没有0这个点（点从1开始，我这样写只是为了偷懒，只要理解这里赋极大值就可）
        for(int i=1;i<=n;++i)//遍历所有点
        {
            if(!used[i]&&minn>dis[i])//找出那个不在集合里面但是又离集合最近的点
            {
                minn=len[i];
                now=i;
            }
        }
        used[now]=1;//标记点已经走过
        tot++;//表示集合里的点数+1
        for(int i=head[now];i;i=bian[i].qian)//以此点为中转
        {
            int v=bian[i].wei;//v是与now相连的点
            if(len[v]>bian[i].quan&&!used[v])//如果不在集合里并且可以更新len
            {
                len[v]=bian[i].quan;//那就更新
            }
        }
    }
}

很容易就能看出，这个算法的复杂度是n二次方的，不知道大家是否还记得dji的优化算法，哈哈，这里依旧适用，可以优化到nlogn，具体就不详述了，可以去看看我关于堆优化的dji的讲解，多说一句，这个算法适合点少边多的图，如果点特别多这个算法还是不太行，毕竟是一个个找点的算法，下篇介绍克鲁斯卡尔算法，是适合点多边少的一个算法！