最小生成树是图论里很重要的部分。但是由于它属于图论所以NOIP基本不考，对于NOI又太基础，所以竞赛中出现的几率比较小，即使要考也不可能考裸的生成树算法= =
最小生成树就Prim和Kruskal两个算法，又没有多大的优化余地，所以学习起来还是很简单的。
一.Prim算法
1.算法思想
对于图G=(V,E)，用Prim算法求最小生成树T=(S,TE)的流程如下
① 初始化：设S、TE为空集，任选节点K加入S。
② 选取一条权值最小的边（X,Y），其中X∈S，且not (Y∈S） 即，选取一条权值最小的、连接着S中一点与S外一点的边。
将Y加入S中，边（X，Y）加入TE中
重复② 直到V=S即所有G中的点都在S中，此时的T为G的最小生成树。
由此流程可见，Prim算法求最小生成树时任何时候的T都是一颗树。
2.实现
显然，Prim算法的主要运行时间花在过程②的选边中。看起来复杂度是O(VE)=O(V^3)不是么，效率也太低了吧……
为了比较快速地选边，我们用两个数组lowcost、closest动态地维护每一个点到S的最短距离。在某一状态下，lowcost[i]表示所有与i相连且另一端点在S中的边中的权值最小值，closest[i]表示在S中且与i相连的点中与i之间距离最小的点。显然，lowcost[i]=w(i,closest[i])。需要注意的是两个数组记录的都是边而不是路径。若i没有边直接连向S，则lowcost[i]=∞。另外，若i已在S中，则lowcost[i]=0。
设出发点为x。初始时对于任意k∈V，closest[k]=x，lowcost[k]=w（k,x）【w（i，j）表示i、j间的距离。初始化时，若两点间没有边则w（i，j）赋为一个足够大的整数（如maxint），并且所有点到自身的距离赋为0，即w（i，i）=0】
每一次找出lowcost中不为0的最小值lowcost[i]，然后把i加入S（即lowcost[i]:=0），然后对于图中所有点k，若w(k,i)
以上操作重复|V|-1次结束。由于每次加入S的点i都在当时取到了符合流程②的边min{lowcost}，而lowcost[i]=w(i,closest[i])，所以此时的最小生成树的各边就是(i,closest[i])，i∈V且not (i=x)【需要注意的是出发点x的closest[x]还是x，所以应忽略，实际取到x-1条边】。把i从1取到|V|，便得到最小生成树T的每条边。
Pascal程序：（摘自NOCOW，略有改动）
（设边权存于数组cost，图的顶点个数|V|为n）
不难看出，以上算法包含一个二重循环，算法复杂度为O（V^2），与图的稠密度无关。
3.使用堆优化
如果我们把要取的边作为一个最小优先级队列，用堆来选取边与调整，则算法可以得到优化。
对于上面代码绿色部分，转换成堆后就是一个建立一个有V个节点的小根堆的过程，复杂度为O（V）；对于红色部分，就是取堆顶元素【O（1）】并删除、维护【O（logV）】；对于橙色部分，对于for循环我们可以用一个数组edge[i]记录与i节点相连的所有边，这样我们就把for循环的复杂度变成了与E相关。显然，图中的每条边仅在其两顶点进入最小生成树时被访问一次，也就是每条边被访问2次，因此橙色部分的执行次数总共是2E次而与外面的while无关。里面的lowcost修改时需要维护堆，复杂度为O（logV）。因此，算法的总复杂度为O（VlogV+ElogV）=O（ElogV）。具体程序见本文最下方。
对于|E|接近|V|的稀疏图，算法复杂度接近O（VlogV）显然比O（V^2）的算法优秀很多。然而对于E接近N^2的稠密图，算法复杂度接近O（V^2logV）反而不如平方算法。因此，使用堆优化的Prim算法适用于稀疏图，而不优化的Prim算法适用于稠密图。不过O（V^2logV）实际上不比O(V^2)慢多少，而现在的题目大多是稀疏图，所以这个算法在总体上是优于朴素Prim算法的。
顺便一提，如果用斐波那契堆来做的话，时间复杂度可以进一步优化为O（E+VlogV）。但事实上这样做的代码长度会到令人发指的地步，所以是一种只存在于论文的算法。应付一般的竞赛用堆优化的Prim就可以应付所有数据了。
二.Kruskal算法
1.算法思想
设最小生成树为T=（V，TE），初始时设TE为空集。将G中所有边按权值排序，从小到大选取边。若当前选取的边加入TE后不会使TE出现环，则将边加入TE，否则舍弃之。当TE中有n-1条边时，算法结束。此时T=（V,TE)为G的最小生成树。
关于判断是否会产生环，有一个简单的方法：若i与j中已有一条路径i-k1-k2-…-kn-j，若加入边（i，j）就会形成环【i-k1-k2-…-kn-j-i】。因此，若一条边连接两个连通分量就不会形成环，反之则会形成环。初始时每一个点就是一个连通分量，当加入（i，j）时，判断i与j是否属于不同连通分量。如果是的话，在加入边后把i与j所在的连通分量合并。重复以上操作，就可以保证不会产生环。
2.实现
显然，Kruskal的难点在于判断、合并连通分量。Pascal语言中已有集合类型可以实现这一操作，不过竞赛中set是一个极其危险的类型【基本常识】。此处只用到查询、合并两个操作，是一个很明显的并查集模型，每一个连通分量就是并查集里的一个集合，通过并查集的算法即可实现算法。
3.时间复杂度分析
对E条边排序的复杂度为O（ElogE）；E次并查集的查找、合并的复杂度也约为O（ElogE），因此算法的复杂度为O（ElogE）。又由于|E|的取值范围为【|V|-1】～【|V|(|V|-1)/2】=【|V|】～【|V|^2】，所以log|E|的范围是【log|V|】～【2log|V|】。因此O（logE）可以写作O（logV）。为了方便与Prim算法复杂度的比较，一般来说把Kruskal的复杂度表述为O（ElogV）
三、Prim、Kruskal、Prim+Heap算法效率实测
评测环境：WindowsXP，FreePascal2.40，Pentium（R） Dual-Core CPU T4300@2.10GHz，2G内存
通过上图可以看出：
1.Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。
2.Prim+Heap在任何时候都有令人满意的的时间复杂度，但是代价是空间消耗极大。【以及代码很复杂>_<】
3.时间复杂度并不能反映出一个算法的实际优劣。
竞赛所给的题大多数是稀疏图，所以尽可能地使用Prim+Heap吧，在稀疏图中这是无敌的。如果一定要在朴素Prim和Kruskal里选一个的话那就用Kruskal吧。当然Prim的代码比较简单，对付水题用Prim也无所谓，只要不是极稀疏图两者相差不大。
最后附上Pascal写的Prim+Heap程序：
此处为了优化时间复杂度，把邻接表和邻接矩阵都用到了，否则对邻接矩阵的初始化都要n^2的时间，比整个ElogV的算法还慢【笑】。这也是堆优化的Prim容易超空间的原因= =【cost-n^2，edge-n^2，lowcost、closest、heap、arc-4×n====>2n^2+4n……】
当然，邻接矩阵实际上根本用不上，把邻接表的基类型改成record记录端点和权值就省掉了n^2的空间，但是……实际上是我太懒了【小声】
const maxn=12000;
var n,m,tot:longint;
cost:array[1..maxn,1..maxn] of longint;
edge:array[1..maxn,0..maxn] of longint;
lowcost,closest,heap,arc:array[1..maxn] of longint;
heapsize:longint;
procedure init;
var i,j,k,l:longint;
begin
readln(n,m);
for i:=1 to m do begin
readln(j,k,l);
cost[j,k]:=l;
cost[k,j]:=l;
inc(edge[j,0]);
edge[j,edge[j,0]]:=k;
inc(edge[k,0]);
edge[k,edge[k,0]]:=j;
end;
for i:=1 to n do begin
lowcost[i]:=maxlongint;
closest[i]:=-1;
heap[i]:=i;
arc[i]:=i;
end;
lowcost[1]:=0;
heapsize:=n;
tot:=0;
end;
procedure shift(i:longint);
var l,r,t:longint;
begin
l:=2*i;
r:=2*i+1;
if (l<=heapsize) and (lowcost[heap[l]]
if (r<=heapsize) and (lowcost[heap[r]]
if t<>i then begin
l:=heap[i];
heap[i]:=heap[t];
heap[t]:=l;
arc[heap[t]]:=t;
arc[heap[i]]:=i;
shift(t);
end;
end;
procedure prim_heap;
var i,j,k,l,t:longint;
begin
for i:=n div 2 downto 1 do
shift(i);
for i:=1 to n do begin
j:=heap[1];
if closest[j]<>-1 then begin
inc(tot,cost[j,closest[j]]);
writeln(j,'-',closest[j]);
end;
lowcost[heap[1]]:=0;
heap[1]:=heap[heapsize];
arc[heap[1]]:=1;
dec(heapsize);
shift(1);
for k:=1 to edge[j,0] do
if cost[edge[j,k],j]
lowcost[edge[j,k]]:=cost[edge[j,k],j];
l:=arc[edge[j,k]];
while (l>1) and (lowcost[heap[l div 2]]>lowcost[heap[l]]) do
begin
t:=heap[l];
heap[l]:=heap[l div 2];
heap[l div 2]:=t;
arc[heap[l]]:=l;
arc[heap[l div 2]]:=l div 2;
l:=l div 2;
end;
closest[edge[j,k]]:=j;
end;
end;
writeln('Total=',tot);
end;
begin
assign(input,'graph.in');
assign(output,'tree.out');
reset(input);
rewrite(output);
init;
prim_heap;
close(input);
close(output);
end.