prims算法（prim算法过程图解）



最小生成树在生活中可以运用到许多实际的问题。例如在n个城市之间建立通信网络，很容易知道至少要架设n-1条线路，每条线路可能因为路程、地势等多方面原因，造价可能也不同，怎么设计出造价最小的线路，并且使每个城市都互联。最小生成树就能给出答案。

下面我们来看看最小生成树的两种经典算法。

Prim（普里姆）算法：（割边）

PRIM算法 基本思想：

（V代表定点，E代表边）假设N=(V,{E})是联通网，TE是N上的最想生成树中的变得集合。算法从 U={u0}(u0属于V)，TE={}开始，重复执行下述操作：在所有的u属于U，v属于V-U的边（u，v）属于E中找到一条代价最小的（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE}) 为N的最小生成树。
下面我们用一张图就能很清楚的了解Prim算法的思想。

（1）首先将A结点加入到集合，取权值最小的边（19）将F连接起来，割掉其他边； 

（2）再将F加入集合，取除了与A相连的另外几条最小的边，这里权值最小边有两条（25），选择其中一条（与C结点相连的边），并割掉其他边； 

（3）重复以上步骤，直到所有的顶点都加入到集合中。从而形成的就是这个图权重最小的情况。  

当然最小生成树并不唯一。

Kruskal的基本思想： 
克鲁斯卡尔算法从另一个途径求网中的最小生成树。假设联通网N=(V,{E})，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点各自构成一个连通分量。 在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条最小的边。以此类推，直至T中所有的顶点都在同一连通分量上为止。
我们同样用一张图来了解Kruskal的基本思想。

kruskal 首先将所有的边都去掉，然后再所有边中找到权重最小的边，并将两个连通分量连接成一个，就把边加入到集合。这里第一次边的权重最小的是1，将权重为1所在的边的顶点连接，形成一个连通分量。接着最小边依然是1，并且能将两个连通分量连接成一个连通分量，所以在此把1所在的边加上。以此类推，知道形成一个连通分量为止。

简单实现。读者可以简单琢磨一下，里面注释比较详细：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/77388.html