最小生成树&Prim算法.ppt

四、最小生成树(minimumcostspanningtree)用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。
按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。
构造最小生成树的准则：
必须只使用该网络中的边来构造最小生成树；
必须使用且仅使用n-1条边来联结网络中的n个顶点；
不能使用产生回路的边。最小生成树（MSTminimalspanningtree）的重要性质：
设G=（V，E）是一个连通网络，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中u∈U,v∈V-U,则一定存在G的一棵包括（u，v）的最小生成树。证明（反证法）：
假设G中任何一棵最小生成树中都不包含(u，v)。设T是一棵最小生成树但不包含(u，v)。由于T是最小生成树，所以T是连通的，因此有一条从u到v的路径，且该路径上必有一条连接两个顶点集U、V的边(u，v)，其中u∈U，v∈V-U。当把边(u，v)加入到T中后，得到一个含有边(u，v)的回路。删除边(u，v)，上述回路即被消除。由此得到另一棵生成树T，T和T的区别仅在于用边(u，v)代替了(u，v)。由于(u，v)的权<=(u，v)的全权，所以，T的权<=T的权，与假设矛盾。u普里姆(Prim)算法用普里姆(Prim)算法构造最小生成树的过程普里姆算法构造的基本思想侯选集的调整方法：
当最短紫边(u,v)被涂成红色被加入T中后，v由蓝点变为红点，对每一个剩余的蓝点j，边(v,j)就由非紫边变成了紫边，这就使得我们必须对侯选集做如下调整：若侯选集中蓝点j所关联的原最短紫边长度大于新紫边(v,j)的长度，则以(v,j)作为j所关联的新的最短紫边来代替j的原最短紫边，否则j的原最短紫边不变。Prim算法的结构如下：

(1)置T为任意一个顶点，置初始侯选紫边集；
(2)while(T中顶点数目<n)
(3){从侯选紫边集中选取最短紫边(u,v);
(4)将(u,v)及蓝点v涂成红色，扩充到T中；
(5)调整侯选紫边集；
(6)}PRIM算法
typedefstruct
{intfromvex,endvex;
floatlength;
}edge;
floatdist[n][n];
edgeT[n-1];

PRIM()
{intj,k,m,v,min,max=10000;
floatd;
edgee;
for(j=1;j<n;j++)
{T[j-1].fromvex=1;
T[j-1].endvex=j+1;
T[j-1].length=dist[0][j];
}
算法分析