生成树是图的极小连通子图(遍历中的每一个点从始点出发只能通过一条路径到达，而没有包括那些不必要的边)。
最小生成树是使得各边上的权值总和达到最小的生成树。
克鲁斯卡尔算法(属贪心法)：先将所有的结点分别放到一个集合中，将所有的边按权构成最小堆，每次从堆顶取一条边，如果所连的两个结点不在一个集合中，就选择这条边，并将这两个点放入一个集合中。直到选择的边数等于顶点数-1时算法结束。
注意在使用这个算法前要建立KruskalEdge边节点，包括两个顶点域和一个权值域，再重载比较大小的运算(返回比较权值的大小的结果)，以用于堆及其向上向下调整。
*Kruskal注解
template<class ElemType,class WeightType>
void Kruskal(const NetWork<ElemType,WeightType> &g)
{
int count=0;//初始化边计数器
int VexNum=g.GetVexNum();//顶点总数
KruskalEdge<ElemType,WeightType> KEdge;//临时对象,用于赋值后插入堆
MinHeap<KruskalEdge<ElemType,WeightType>> ha(g.GetEdgeNum());//构造能存所有边的空堆
ElemType v1,v2;//顶点类型,辅助操作(和临时对象KEdge之间的桥梁)
/*初始化并查集*/
ElemType *kVex=new ElemType[VexNum];//开辟顶点数组,用来构造并查集
for(int i=0;i<VexNum;i++)//将顶点赋值到顶点数组中
g.GetElem(i,kVex[i]);
UFSets<ElemType> f(kVex,VexNum);//根据顶点数组构造并查集
/*初始化最小堆*/
for(int v=0;v<g.GetVexNum();v++)//对每个顶点
for(int u=g.FirstAdjVex(v);u>=0;u=g.NextAdjVex(v,u))//对它的所有邻接点
if(v<u)//无向图不妨只看上三角表
{
g.GetElem(v,v1);//取v对应顶点给v1
g.GetElem(u,v2);//取u对应顶点给v2
KEdge.vertex1=v1;
kEdge.vertex2=v2;
kEdge.weight=g.GetWeight(v,u);//为临时对象三个域赋值
ha.Insert(KEdge);//将临时对象插入堆中,堆中自会向上调整
}
/*核心算法*/
while(count<VexNum-1)//边计数器达到顶点数-1即算法结束
{
ha.DeleteTop(KEdge);//删除堆顶元素存入临时对象中去,堆中自会向下调整
v1=KEdge.vertex1;
v2=KEdge.vertex2;//从这个被删的堆顶元素中取顶点信息
if(f.Differ(v1,v2))//如果v1,v2不在同一集合中
{
cout<<"边:("<<v1<<","<<v2<<")权:"<<KEdge.weight<<endl;//选择(输出)这条边
f.Union(v1,v2);//合并为同一集
count++;//边计数器+1
}
}
}
时间复杂度：O(e*log[2]e)，适用于点多边少(稀疏的)连通网络。
普里姆算法(属动态规划)：先任意找一个顶点放入大集合(后面称U集)中，然后找U集外到这个U集中有最短距离的点，加入到这个U集中，然后更新U集外的点到这个集合的距离，如此反复。最后所有的点都在U集中时算法结束。
算法中用一个辅助数组closearc[]来记录谁在U集中(lowweight域为0)，谁在U集外(lowweight非0)，并记录产生这个最短距离的U集内的那个点游标给nearvertex域，在挑选边时用到。
*Prim注解
template<class ElemType,class WeightType>
struct CloseArcType//辅助数组的节点
{
//这两个域需同步刷新
WeightType lowweight;//当前到U集的最短距离
int nearvertex;//当前到U集中的哪个节点具有该最短距离
};
template<class ElemType,class WeightType>
void Prim(const NetWork<ElemType,WeightType> &g,int u0)//从u0开始构建图g的最小生成树
{
WeightType min;//临时存储最小距离
ElemType v1,v2;
int u,v,k;
int vexnum=g.GetVexNum();//顶点数目
if(u0<0 || u0>=vexnum)//如果u0范围不合法
throw Error("顶点u0不存在");//抛掷异常
//为辅助数组申请空间
CloseArcType<ElemType,WeightType> *closearc=new CloseArcType<ElemType,WeightType>[vexnum];
/*初始化辅助数组*/
for(v=0;v<vexnum;v++)//对辅助数组中每个点
{
closearc[v].nearvertex=u0;//u0以外的其它点都到u0最短(U集一开始只有u0)
closearc[v].lowweight=g.GetWeight(u0,v);//v到u0的距离就是当前到U集最短距离
}
closearc[u0].nearvertex=-1;//u0标记这个域为-1
closearc[u0].lowweight=0;//表示u0一开始就在U集中
/*核心算法*/
for(k=1;k<vexnum;k++)//对除了u0外的其它vexnum-1个顶点(k仅表示循环次数,循环里没用到)
{
min=g.GetInfinity();//先取最小距离为无穷,保证一定能正确更新
v=u0;//v记录具有最小距离的U集外的点,开始给个u0,在循环里刷新
/*寻找U集外有最短距的点v*/
for(u=0;u<vexnum;u++)//对辅助数组里的每个点
if(closearc[u].lowweight!=0 && closearc[u].lowweight<min)//如果不在U集且距离更小
{
min=closearc[u].lowweight;//就刷新最小,给min
v=u;//并记录u,给v
}
if(v!=u0)//找到了最小边对应的U集以外的那个点
{
g.GetElem(closearc[v].nearvertex,v1);//这个边对应U集内的点v1是U集外那个v的nearvertex域
g.GetElem(v,v2);//U集外点对应游标v所对应的点名也给v2
cout<<"边:("<<v1<<","<<v2<<")权:"<<min<<endl;//输出(选择)这条边
closearc[v].lowweight=0;//将这个外点变成U集的内点
/*看看新加入的点v或许会更新辅助数组*/
for(u=g.FirstAdjVex(v);u!=-1;u=g.NextAdjVex(v,u))//对于v所有的邻接点u
//如果u在U集外，且到新加入的v的距离比之前记录的到U集的最小距离还小
if(closearc[u].lowweight!=0 && (g.GetWeight(v,u)<closearc[u].lowweight))
{
closearc[u].lowweight=g.GetWeight(v,u);//更新到U集的最小距离
closearc[u].nearvertex=v;//产生这个最小距离的U集中的点游标也变成了v
}
}
}
delete []closearc;//算法结束,释放辅助数组空间
}
时间复杂度：O(n^2)，适用于点少边多(密集的)连通网络。