数据结构(java版)图2(最小生成树).ppt

最小生成树主要内容生成树与最小生成树最小生成树的应用如何求图的最小生成树Prim算法求最小生成树Kruskal算法求最小生成树实践项目:编一程序实现Prim和Kruskal算法生成树与最小生成树生成树:在一个连通图G中,如果取它的全部顶点和一部分边构成一个子图G’,即 V(G’)=V(G),E(G’)E(G),若边集E(G’)中的边将图中所有的顶点连通又不形成回路,则称子图G’为图G的一棵生成树。*一棵有n个顶点的生成树有且仅有n-1条边,但有n-1条边的图不一定是生成树。最小生成树:具有权最小的生成树。生成树举例由生成树的定义可知:①若在生成树中删除一条边,就会使该生成树变成非连通图而不再是生成树。②若在生成树中再增加一条边,就会使该生成树因为存在回路而不再是生成树。③一个连通图的生成树可能有多个。④n个顶点的连通图的生成树有且仅有n-1条边。最小生成树举例从最小生成树的定义可知,构造n个顶点的无向带权连通图的最小生成树,必须满足如下三个条件:①必须包含n个顶点。②有且仅有n-1条边。③没有回路。,主要目标是要使这n个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同;另一个目标是要使铺设光缆的总费用最低。,(Prim)(从点着手)适合于求边稠密的最小生成树克鲁斯卡尔算法(Kruskal)(从边着手)适合于求边稀疏的最小生成树普里姆算法(Prim)思想令集合U={u0}(即从顶点u0开始构造最小生成树),集合T={}。从所有顶点u∈U和顶点v∈V-U的边权中选择最小权值的边(u,v),将顶点v加入到集合U中,边(u,v)加入到集合T中。如此重复下去,直到U=V时则最小生成树构造完毕。此时集合U就是最小生成树的顶点集合,集合T就是最小生成树的边集。普里姆算法(Prim)构造最小生成树过程普里姆(Prim)算法设计prim(带权无向连通图graph){ tree=null;//最小生成树edges=按权值大小排序; for(i=1;i<n;i++)//n是顶点数 for(j=1;j<=边数;j++) if(egdgs中的边ej和tree中的边不产生回路且和tree中的一个顶点关联) {将ej边加入到tree中; break;}}