数据结构教学全套课件Java版杨淑萍教学资料教学演示文稿 图2最小生成树.ppt

《数据结构教学全套课件Java版杨淑萍教学资料教学演示文稿 图2最小生成树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最小生成树主要内容生成树与最小生成树最小生成树的应用如何求图的最小生成树Prim算法求最小生成树Kruskal算法求最小生成树实践项目:编一程序实现Prim和Kruskal算法生成树与最小生成树生成树：在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即V(G’)=V(G)，E(G’)E(G),若边集E(G’)中的边将图中所有的顶点连通又不形成回路，则称子图G’为图G的一棵生成树。*一棵有n个顶点的生成树有且仅有n-1条边，但有n-1条边的图不一定是生成树。最小生成树：具有权最小的生成树。生成树举例由生成树的定义可知：①若在生成树中删除一条边

2、，就会使该生成树变成非连通图而不再是生成树。②若在生成树中再增加一条边，就会使该生成树因为存在回路而不再是生成树。③一个连通图的生成树可能有多个。④n个顶点的连通图的生成树有且仅有n-1条边。最小生成树举例从最小生成树的定义可知，构造n个顶点的无向带权连通图的最小生成树，必须满足如下三个条件：①必须包含n个顶点。②有且仅有n-1条边。③没有回路。最小生成树应用建立城市光缆.要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。求解最小生成树问题

3、实质上是最小代价问题.类似的问题还有城市之间高速公路建设问题,物流系统中运费最低问题等.求最小生成树算法普里姆算法（Prim）(从点着手)适合于求边稠密的最小生成树克鲁斯卡尔算法（Kruskal）（从边着手）适合于求边稀疏的最小生成树普里姆算法（Prim）思想令集合U=｛u0｝（即从顶点u0开始构造最小生成树），集合T=｛｝。从所有顶点u∈U和顶点v∈V-U的边权中选择最小权值的边(u,v)，将顶点v加入到集合U中，边(u,v)加入到集合T中。如此重复下去，直到U=V时则最小生成树构造完毕。此时集合U就是最小生成树的顶点集合，集合T就是最小生成树的边集。普里

4、姆算法（Prim）构造最小生成树过程普里姆（Prim）算法设计prim(带权无向连通图graph){tree=null;//最小生成树edges=按权值大小排序；for(i=1;i

5、即初始时，最小生成树的边集为空，顶点集合为图G的全部顶点。这样，如果把T中每个顶点看作一个一个连通分量，然后按照边的权值递增顺序逐条考察图G中的边，若被考察的边两个顶点属于2个不同的连通分量中，则将该条边加入到生成树T中，同时把2个连通分量合成一个连通分量。如此继续下去，当T中的连通分量成为一个时，T中的这个连通分量就是图G的一棵最小生成树。克鲁斯卡尔算法最小生成树构造过程克鲁斯卡尔Kruskal算法设计kruskal(带权无向连通图graph){tree=null;//最小生成树edges=按权值大小排序；for(i=1;i<边数&&tree的顶点数<=n

6、;i++)//n是顶点数if（egdgs中的边ej和tree中的边不产生回路且和tree中的一个顶点关联）将ej边加入到tree中；}实践项目设计一个程序实现Prim和Kruskal算法.扫描次数closest[0]closest[1]closest[2]closest[3]closest[4]closest[5]closest[6]初始状态0000000100011002000414030034133400341335006413360064133表5-1lowcost[]数组数据变化情况表5-2closest[]数组数据变化情况扫描次数closest[0

7、]closest[1]closest[2]closest[3]closest[4]closest[5]closest[6]初始状态0000000100011002000414030034133400341335006413360064133