数据结构最小生成树学习教案.pptx

《数据结构最小生成树学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构最小生成树学习教案.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)最小生成树最小生成树第一页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举例举例1.1.求一条从顶点求一条从顶点(dngdin)i(dngdin)i到顶点到顶点(dngdin)s(dngdin)s的简单路径的简单路径2.2.求两个求两个(lin)(lin)顶点之间的一条长度最顶点之间的一条长度最短的路径短的路径第1页/共49页第二页，共49页。图的遍历图的遍历(bin l)(bin l)应用举例应用举例1.1.求一条从顶点求一条从顶点(dngdin)i(dngdin)i到顶点到顶点(dngdin)s(dngdin)s的简单路径

2、的简单路径求从顶点(dngdin)b到顶点(dngdin)k的一条简单路径。abchdekfg从顶点b b出发进行深度优先搜索遍历第2页/共49页第三页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举例举例求从顶点b到顶点k的一条(y tio)简单路径。假设找到的第一个邻接(ln ji)点是a,且得到的结点访问序列为:b a c h d e k f g假设找到的第一个邻接点是g,则得到的结点访问序列为:b g f k e a d h cabchdekfg第3页/共49页第四页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举例举例1.从顶点从顶点 i

3、到顶点到顶点s,若存在路径，则从顶点若存在路径，则从顶点 i 出发进出发进行深度行深度(shnd)优先搜索，必能搜索到顶点优先搜索，必能搜索到顶点s。2.简单简单(jindn)路径可能有多条。路径可能有多条。3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。结论：结论：第4页/共49页第五页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举举例例void DFSearch(int v,int s,char*PATH)/从第从第v个顶点出发个顶点出发(chf)递归地深度优先遍历图递归地深度优先遍历图G，/求得一条从求得一条从v到到s的简单路径，并记录在的简单路径，

4、并记录在PATH中中 visitedv=TRUE;/访问第访问第 v 个顶点个顶点 for(w=FirstAdjVex(v);w=0;w=NextAdjVex(v)if(!visitedw)DFSearch(w,s,PATH);Append(PATH,getVertex(v);/第v个顶点(dngdin)加入路径if(w=s)found=TRUE;Append(PATH,w);break;else if(!found)Delete(PATH);/从路径上删除顶点 v 第5页/共49页第六页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举例举例2.2.求两个求两个(lin)

5、(lin)顶点之间的一条长度顶点之间的一条长度最短的路径最短的路径 若两个顶点之间存在多条路径(ljng)，则其中必有一条路径(ljng)长度最短的路径(ljng)。如何求得这条路径(ljng)?第6页/共49页第七页，共49页。图的遍历图的遍历(bin l)(bin l)应用举应用举例例abchdekfg求从顶点(dngdin)b到顶点(dngdin)k的一条路径长度最短的路径。第7页/共49页第八页，共49页。图的遍历图的遍历(bin l)(bin l)应用举例应用举例abchdekfgabchdekfg广度优先广度优先(yuxin)搜索访问顶点的次搜索访问顶点的次序是按序是按“路径长度路

6、径长度”渐增的次序。渐增的次序。广度优先搜索是使用广度优先搜索是使用(shyng)“队列队列”实实现的，如何记住路径的所有结点？现的，如何记住路径的所有结点？第8页/共49页第九页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举举例例012345ABCDEF14043525011253BACDFE第9页/共49页第十页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举例举例0 A1 B2 C 3 D4 E5 F6 G7 K1-110001abchdekfg1第10页/共49页第十一页，共49页。图的遍历应用图的遍历应用(yngyng)(yngyng)举

7、例举例怎样修改广度(gungd)优先遍历算法呢？while(!QueueEmpty(Q)DeQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)w.parent=u;if(w=?)found=true;break;if(!visitedw)visitedw=TRUE;EnQueue(Q,w);/for if(found)break;/while/从从w开始往后找祖先开始往后找祖先(zxin)结点，逆向打印结点，逆向打印第11页/共49页第十二页，共49页。生成生成(shn chn)树树一、定义一、定义图图G的生成树是的生成树是G的极小连

8、通的极小连通(lintng)子子图，即包含图，即包含G中的所有顶点（中的所有顶点（n）和）和n-1条边条边的连通的连通(lintng)子图子图第12页/共49页第十三页，共49页。生成生成(shn chn)树树V1V2V3V4V5V8V6V7V1V2V4V8V5V3V6V7V1V2V3V4V5V8V6V7深度深度(shnd)优优先：先：广度广度(gungd)优先：优先：第13页/共49页第十四页，共49页。生成生成(shn chn)树树二、算法二、算法图的遍历算法访问了图中的每个顶点一次图的遍历算法访问了图中的每个顶点一次且仅一次。且仅一次。访问某个顶点的邻接点时，要经过访问某个顶点的邻接点时

9、，要经过(jnggu)与这两个顶点相关联的边。与这两个顶点相关联的边。因此，图的遍历算法可以产生一颗生成因此，图的遍历算法可以产生一颗生成(shn chn)树：所有的顶点和经过的边。树：所有的顶点和经过的边。第14页/共49页第十五页，共49页。生成生成(shn chn)森森林林一、定义一、定义 非连通图非连通图G的每个连通分量的生成的每个连通分量的生成(shn chn)树，构成了图树，构成了图G的生成的生成(shn chn)森森林林第15页/共49页第十六页，共49页。生成生成(shn chn)森森林林abchdekfg812345670812345670achdkfebgabchdekfg

10、非连通非连通(lintng)图图G：G的深度优先搜索生成的深度优先搜索生成(shn chn)森林：森林：第16页/共49页第十七页，共49页。最小生成最小生成(shn chn)树树 假设假设(jish)(jish)要在要在 n n 个城市之间建立个城市之间建立通讯联络网，则连通通讯联络网，则连通 n n 个城市只需要修建个城市只需要修建 n-1n-1条线路，如何在最节省经费的前提下建条线路，如何在最节省经费的前提下建立这个通讯网？立这个通讯网？问题问题(wnt)：第17页/共49页第十八页，共49页。最小生成最小生成(shn chn)树树abcdegf195141827168213127连通网

11、：连通网：n个城市个城市(chngsh)和城市和城市(chngsh)间可能的通信线间可能的通信线路路网的顶点：表示网的顶点：表示(biosh)城市城市网的边：网的边：表示两个城市之间的线表示两个城市之间的线路路网的边上的权值：网的边上的权值：通信代价通信代价第18页/共49页第十九页，共49页。最小生成最小生成(shn chn)树树 构造(guzo)网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。算法算法(sun f)(sun f)二：（克鲁斯卡尔二：（克鲁斯卡尔算法算法(sun f)(sun f)）该问题等价于：该问题等价于：算法三：（普里姆算法）

12、算法三：（普里姆算法）算法一：（破圈法）算法一：（破圈法）第19页/共49页第二十页，共49页。破圈法破圈法一、基本思想1、如果图G是一个连通图，但不是树，则边数n-1，图中一定存在回路（环/圈）。2、将所有的边按权重从大到小排列3、对每条边e尝试(chngsh)下面的操作，直到G中的边数=n-1 如果删除e,图G仍然是连通图，则从G中删除e，否则，保留e。第20页/共49页第二十一页，共49页。破圈法破圈法abcdegf195141827168213127二、示例(shl)(venum=7,arcnum=11,67)第21页/共49页第二十二页，共49页。克鲁斯卡尔算法克鲁斯卡尔算法(sun

13、 f)具体做法具体做法:先构造一个先构造一个(y)(y)只含只含n n个顶点的子个顶点的子图图SGSG，然后从权值最小的边开始，若它的添加不，然后从权值最小的边开始，若它的添加不使使SGSG中产生回路，则在中产生回路，则在SGSG上加上这条边，如此重上加上这条边，如此重复，直至加上复，直至加上n-1n-1条边为止。条边为止。考虑问题的出发点考虑问题的出发点:为使生成为使生成(shn chn)(shn chn)树上树上边的权值之和达到最小，则应使生成边的权值之和达到最小，则应使生成(shn(shn chn)chn)树中每一条边的权值尽可能地小。树中每一条边的权值尽可能地小。第22页/共49页第二

14、十三页，共49页。克鲁斯卡尔算法克鲁斯卡尔算法(sun f)abcdegf3abcegfd 21581416第23页/共49页第二十四页，共49页。克鲁斯卡尔算法克鲁斯卡尔算法(sun f)算法算法(sun f)(sun f)描述描述:构造非连通图构造非连通图 ST=(V,);ST=(V,);k=i=0;/k k=i=0;/k 选中的边数选中的边数 while(kn-1)while(kn-1)+i;+i;检查检查(jinch)(jinch)边集边集E E中第中第i i条权值最小的边条权值最小的边(u,v);(u,v);if if 若若(u,v)(u,v)加入加入STST后不使后不使STST中产

15、生回路，中产生回路，则输出边则输出边(u,v);(u,v);且且k+;k+;第24页/共49页第二十五页，共49页。普里姆算法普里姆算法(sun f)在生成树的构造过程中，图中在生成树的构造过程中，图中n n个顶点分属两个集合个顶点分属两个集合(jh)(jh)：已落在生成树上的顶点集：已落在生成树上的顶点集U U和尚未落在生成树上的顶和尚未落在生成树上的顶点集点集V-UV-U，则应在所有连通，则应在所有连通U U中顶点和中顶点和V-UV-U中顶点的边中选取权中顶点的边中选取权值最小的边。值最小的边。UV-U第25页/共49页第二十六页，共49页。普里姆算法普里姆算法(sun f)abcdegf

16、195141827168213127abegf14d8c351621g b dg b fc 第26页/共49页第二十七页，共49页。普里姆算法普里姆算法(sun f)算法的核心：选择向集合U中加入(jir)的顶点时，要选择到U具有最短边的顶点1、对任何一个顶点v，如果(rgu)它有多个邻接U的边，则需要找出最短的边作为邻接到U的边2、从所有的V U顶点中，找出具有最短边的顶点，将它加入U第27页/共49页第二十八页，共49页。普里姆算法普里姆算法(sun f)技巧：技巧：设置设置(shzh)(shzh)一个辅助数组，对当前一个辅助数组，对当前V VU U集中的每集中的每个顶点，记录和顶点集个顶

17、点，记录和顶点集U U中顶点相连接的代价最小中顶点相连接的代价最小的边：的边：struct VertexType adjvex;/U集中集中(jzhng)的顶点序号的顶点序号 VRType lowcost;/边的权值边的权值 closedgeMAX_VERTEX_NUM;第28页/共49页第二十九页，共49页。普里姆算法普里姆算法(sun f)初始(ch sh)时U=v0对wV U，closedgew.lowcost=或者(huzh)=closedgew.adjvex=v0当U=U u时，对wV U，修改closedgewclosedgew.lowcost=或者不变closedgew.adjv

18、ex=u第29页/共49页第三十页，共49页。普里姆算法普里姆算法(sun f)abcdegf195141827168213127aedcbaaa19141814e12ee8168d3dd7213c55第30页/共49页第三十一页，共49页。普里姆算法普里姆算法(sun f)void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法(sun f)从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek

19、.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i)继续向生成继续向生成(shn chn)树上添加顶点树上添加顶点;第31页/共49页第三十二页，共49页。普里姆算法普里姆算法(sun f)k=minimum(closedge);/求出加入生成(shn chn)树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk,closedgek.lowcost);/输出生成(shn chn)树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.

20、adj adjvex;DFSArticul(G,v);/从第v顶点出发深度(shnd)优先搜索 if(count nextarc)min=visitedv0=+count;/v0是第count个访问(fngwn)的顶点,并设lowv0的初值为min/检查v0的每个邻接点lowv0=min;第44页/共49页第四十五页，共49页。关节点和重连通关节点和重连通(lintng)图图 w=p-adjvex;/w为v0的邻接顶点 if(visitedw=0)/w未曾被访问(fngwn)DFSArticul(G,w);/返回前求得loww else /w是回边上的顶点if(loww=visitedv0)p

21、rintf(v0,G.verticesv0.data);/输出输出(shch)关节点关节点if(visitedw=0;w=NextAdjVex(G,v,w)if(!visitedw)p=(CSTree)malloc(sizeof(CSNode);*p=GetVex(G,v),NULL,NULL;if(first)T-lchild=p;first=FALSE;else q-nextsibling=p;q=p;DFSTree(G,w.q);/end of if/end of DFSTreeSG1SG2SG3Vw1w3w2第47页/共49页第四十八页，共49页。生成生成(shn chn)森森林林二、算法以孩子兄弟二、算法以孩子兄弟(xingd)链表作为生成森林的存储结链表作为生成森林的存储结构构void DFSForest(Graph G,CSTree&T)T=NULL;for(v=0;v=G.vexnum;+v)visitedv=FALSE;for(v=0;v=G.vexnum;+v)if(!vistedv)p=(CSTree)malloc(sizeof(CSNode);*p=GetVex(G,v),NULL,NULL;if(!T)T=p;else q-nextsibling=p;q=p;DFSTree(G,v,p);第48页/共49页第四十九页，共49页。