1. 普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法的比较
（1）普里姆(Prim)算法：
算法特点：该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集，V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始，并逐渐生长直至U=V，即T包含了 C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小，因此这是一种"贪心"的策略。
算法分析：该算法的时间复杂度为 O(n )。与图中边数无关，该算法适合于稠密图
（2）克鲁斯卡尔(Kruskal)算法：
算法特点：该算法的特点是：当前形成的集合T除最后的结果外，始终是一个森林。
算法分析：该算法的时间复杂度为O(elge)。Kruskal算法的时间主要取决于边数。它较适合于稀疏图。
普里姆(Prim)算法比克鲁斯卡尔(Kruskal)算法更容易实现，而且普里姆(Prim)算法适合于稠密图，所以选择普里姆(Prim)算法构造最小生成树

 

第三章 程序设计思想

3-1 用Prim算法构造最小生成树

3-1-1 算法思想
   T=(U，TE)是存放MST的集合。①T的初值是({r}，￠) 即最小生成树初始时只有一个红点r，没有红边。②T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树⒈选择紫边集中一条轻边并扩充进T⒉将轻边连接的蓝点改红点⒊将轻边改红边⒋修改紫边集
3-1-2 较小紫边集的构造  
若当前形成的T中有k个顶点，|U|=k，|V-u|=n-k，故可能的紫边数目是k(n-k)。从如此大的紫边集中选择轻边是低效的。因此，必须构造较小的紫边集。 对于每个蓝点v ∈V-U，从v到各红点的紫边中，只有最短的那一条才有可能是轻边。因此，只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。
3-1-3 候选紫边集合的修改 
当把轻边(u，v)扩充到T时，因为v由蓝变红，故对每个剩余的蓝点j，边(v，j)就由非紫边变为紫边，这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。因此，用长度更小的新紫边取代那些原有的最短紫边。
用java语言动态实现此过程：
步骤：1、首先在文本框内输入城市的个数，即顶点数
2、根据输入的顶点个数点击鼠标分别显示出①②③④⑤……
3、在文本框内分别输入两个城市的名字以及权值，与此同时，在图中自动画出两点之间的连线，并在线的中央显示其权值。
4、根据求最小生成树（最短路径）的方法，用不同的颜色动态演示出它的生成过程。
5、发布到网页上。
Prim算法构造最小生成树的执行过程如下：