最小生成树贪心算法

㈠ 图的最小生成树算法

图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树.

㈡ 利用Prim（普里姆）算法 构造最小生成树 程序

算法同样是解决最小生成树的问题。

其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。

与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。

复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。

Prim算法用于求无向图的最小生成树

设图G =（V，E），其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。

其算法的时间复杂度为O(n^2)

Prim算法实现：

（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）

（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}

㈢ prim和kruscal算法得到的最小生成树是否一样

应该不一样。可以用一个图根据两算法试一下，若一样，再修改图，之后应该就可以了。
（网络或者查书本更加有效……）
构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。
这个过程一直进行到S=V时为止。
Kruskal算法构造G的最小生成树：将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v, w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v, w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止

㈣ 试设计解决tsp问题的贪心算法，分析时间复杂度，试分析是否存在o的有效算法5分

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得咐迟禅到整体最优解，但对范围相当广泛的许多问题他能产生整体最旦蠢优解或者是整体最优解的近似解。

比如最小生成树Kruskal算法，每次在不构成环的前衡尘提下，总是选择权最小的边。
找零钱问题：以人民币1元，2元，5元，10元，20元，50元，100元为例，要求所找的张数最少 背包问题：假设物体重量W1，W2．．．Wn其对应的价值为P1，P2．．．Pn，物体可分割，求装入重量限制为m的背包中的物体价值最大．

㈤ 最短路算法和最小生成树算法有什么区别

两个算法没有什么太多的联系，只能说是想法类似，都用了一定程度的贪心思维。
最短路是要求一点到另外的点的最短路径，只要最短的长度到达就好，除了出发点和终点外一概不管。如果不求一点到所有点的最短路，甚至可以不管所有点是否都联通。
最小生成树则要保证第一所有点都是联通的，不然就称不上是树了，而后保证树的边长度之和最小。

㈥ 基础-11：最小生成树（MST）

最小生成树（minimum spanning tree）是图计算中基本的问题，背后的问题非常直接，假设无向连通图G(V, E)，且E中的每条边e有权值（可以表示距离、价值等），找哗和出一颗树，连接G中所有的边，且连接这棵树的所有边的权值之和最小。在电子制造中，如何以最低的成本连接多个针管便是这一问题。

下面以一个图来对此进行说明：

前面两课中介绍了动态规划和贪心算法，都是用来解决最值问题，本文中的最小生成树很显然也属于此类。最小生成树使用贪心算法，文中会对贪心算法的使用进行说明。

假设mst是最终要求的最小生成树，若A是最小生成树mst边集的子集，如果每次选择一条边(u, v)加入A，并且确保A始终是mst边集的子集，则最终得到的A必然是mst最小生成树的边集。这样的边(u, v)称为A的 安全边 。安全边即为可以选择的边。

为了得到安全边，下面介绍一些概念。无向图G=(V,E)的一个切割(S, V-S)是节点集V的一个划分，如图2所示：

显然，一个切割将图划分为两部分。如果一条边(u,v)，u在S中，v在S-V中，则称边(u,v)横跨切割(S, V-S)。如果集合A中不存在横跨该切割的乱手盯边，则称该切割尊重A；在横跨切割的所有边中，权重最小的边称为轻量级边（注：轻量级边可能不是唯一的）。

下面的定理和推论保证了Kruskal和Prim算法的正确性，感兴趣的童鞋可以自己证明或参考算法导论中的说明。

根据定理1和推论1，构造最小生成树可以有两种方式，一种是切割的角度，一种是森林的角度。切割的角度：先从图中选取一个点n ₁ ，划一个切割({n ₁ }, V-{n ₁ })，然后找这个切割的轻量级边以及这个边在 V-{n ₁ }的节点n ₂ ；然后再划一个切割（{n ₁ , n ₂ }, V-{n ₁ , n ₂ })，再找出对应的轻量级边，薯困...,直到所有的节点，每一步中找到的轻量级边组成的集合为最小生成树中的边。

森林的方式是：首先将每个节点都看成一个连通分量（此时有n个连通分量），寻找连通连接连通分量权值最小的边(u, v)，(u, v)连接的连通分量为C ₁ 和C ₂ ，则(u, v)连接后，合成一个更大的连通分量C ₁₂ （此时有n-1个连通分量）；然后对n-1个连通分量继续实施上述类似的动作，直至最后变成一个连通分量。

切割的角度对应的是Prim算法，森林的方式对应的是Kruskal算法，算法本身都很简单，在此不再赘述，下面两组从算法导论中摘取的图很好地解释了对应的算法。

最小生成树是图计算中的基本算法，理解算法的关键是切割基础上的轻量级边，上文的说明中野间接解释了利用贪心算法的正确性，相对而言，最小生成树是较为简单和基础的算法，是其他算法的基础。