<p><span style="white-space:pre"></span><strong><span style="font-size:14px">最小生成树</span></strong><span style="font-size:12px">在生活中可以运用到许多实际的问题。例如在n个城市之间建立通信网络，很容易知道至少要架设n-1条线路，每条线路可能因为路程、地势等多方面原因，造价可能也不同，怎么设计出造价最小的线路，并且使每个城市都互联。最小生成树就能给出答案。</span></p> 讯享网
下面我们来看看最小生成树的两种经典算法。
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所在的边加上。以此类推，知道形成一个连通分量为止。
简单实现。读者可以简单琢磨一下，里面注释比较详细：
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/174070.html