生成最小生成树

图的最小生成树的方法主要有2个：一个是普里姆（Prim）算法，另一个是克鲁斯卡尔（Lruskal）算法。
普里姆算法的关键之处是：每次如何从生成树T中到T外的所有边中，找到一条最短边。
算法描述：G=(V,E)是一个具有n个顶点的连通图，T=(U,TE）是G的最小生成树，其中，U是T的顶点集，TE是T的边集，U和TE的初值均为空。算法开始时，首先从V中任取一个顶点，将他并入U中，然后只要U是V的真子集，就从那些其中一个端点已在T中，另一个端点仍在T外的所有变种，找到一条最短的边，并把该边和该店并入到T和TE中，如此下去，直到并入所有的点，最后T就是得到的普里姆最小生成树；
克鲁斯卡尔算法的关键之处：判断是否有回路；
算法描述：假设G=(V,E)是一个具有n个顶点的联通网，T=（U,TE）是G中的最小生成树，U的初值等于V，即包含G中全部的顶点，TE的初值为空集，即不包含任何边。克鲁斯卡尔算法的基本思路是：将图G中的边按照权值从小到大的顺序依次选取，若选取的一条边使生成树T不形成回路，则把他并入生成树的边集TE中，保留作为T中的一条边，若选取的一条边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止，此时的T即为图G的最小生成树。