在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。
图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边
下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。
构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。
下面我们考虑一下如何实现这个操作过程的算法。
分析 ：（1）它主要有两项操作：按条件选择一条边和将顶点加入到U集合中；（2）网中的每个顶点不是在U集合中，就是在V-U集合中。为了提高算法的时间、空间效率，我们将为这个算法设计一个辅助数组closedge，用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点，在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值，若该顶点进入U集合，则值为0；另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示： #defineMAX_NUM10struct{intadjvex;floatlowcist;}closedge[MAX_NUM];整个算法的执行过程可以描述为： {初始化closedge数组的内容；选择某个顶点k作为生成树的根结点，并将它加入到U集合中；重复下列操作n-1次：l选择一条满足条件的边；l输出这条边的两个端点；l修改V-U集合中的顶点信息，即与U集合中构成最小权值的边。}假设该网以邻接矩阵的形式给出，则完整的算法为： voidMini_SpanTree(GraphG,intk,intn){//G是网的邻接矩阵，k是生成树根结点的序号，n是网的顶点数目for(j=0;j<n;j++)if(j!=k)closedge[j]={k,G[k][j]};closedge[k].lowcost=0;for(i=1;i<n;i++){k=minmun(closedge);printf(k,closedge[k].adjvex);closedge[k].lowcost=0;//将顶点加入U集合中for(j=0;j<n;j++)if(closedge&&G[k][j]<closedge[j].lowcost)closedge[j]={k,G[k][j]};}}
