书签 分享 收藏 举报 版权申诉 / 16
上传文档赚钱

类型第十五讲图3数据结构绍兴文理学院课件.ppt

  • 上传人(卖家):晟晟文业
  • 文档编号:5070556
  • 上传时间:2023-02-08
  • 格式:PPT
  • 页数:16
  • 大小:1.10MB
  • 【下载声明】
    1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
    2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
    3. 本页资料《第十五讲图3数据结构绍兴文理学院课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
    4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
    5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
    配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    第十五 数据结构 绍兴 文理学院 课件
    资源描述:

    1、 连通网络的连通网络的最小代价最小代价问题问题第第6 6章章 图图(3)(3)设设G=(VG=(V,E)E)是一个连通是一个连通网络,网络,U U是顶点集是顶点集V V的一个非空子集。若的一个非空子集。若(u(u,v)v)是一条具有最小权值是一条具有最小权值(代价代价)的边的边,其中,其中uUuU,vV-UvV-U,则必存在一棵包,则必存在一棵包含边含边(u(u,v)v)的最小生成树。的最小生成树。(证明略证明略)图的应用图的应用 通信网问题。图的顶点之间的边上的权值表示相应的代价,对通信网问题。图的顶点之间的边上的权值表示相应的代价,对于于n n个顶点的连通图可以建立许多不同的个顶点的连通图

    2、可以建立许多不同的生成树生成树。一棵生成树的代价就是树上各边的一棵生成树的代价就是树上各边的代价之和代价之和。各边各边代价之和代价之和最小的那棵生成树称为该连通网的最小的那棵生成树称为该连通网的最小代价生成最小代价生成树树,简称为,简称为最小生成树最小生成树。2 2、求解最小生成树的基础、求解最小生成树的基础 MST MST性质:性质:uvUVUTKSTKS4 47:42 普里姆普里姆(Prim)(Prim)算法和算法和克鲁斯卡尔克鲁斯卡尔(Kruskal(Kruskal)算法是两个利用算法是两个利用MST MST 性质构造最小生成树的算法。性质构造最小生成树的算法。3 3、普里姆算法、普里姆

    3、算法(1)(1)算法思想算法思想 从连通网络从连通网络 N N=V V,E E 中的某中的某一顶点一顶点V(T)=V(T)=u u0 0 出发,选择与它关出发,选择与它关联的具有最小权值的边联的具有最小权值的边(u u0 0,v v),将其,将其 以后每一步从一个顶点在以后每一步从一个顶点在V(T)V(T)中,而另一个顶点不在中,而另一个顶点不在V(T)V(T)中的中的各条边中选择权值最小的边各条边中选择权值最小的边(u u,v v),),把它的顶点把它的顶点v v加入到集合加入到集合V(T)V(T)中中,将其边,将其边(u u,v v)加入到生成树的边集合加入到生成树的边集合E(T)E(T)

    4、中。中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合合V(T)V(T)中为止中为止(直到直到V(T)V(T)满满n n个顶点为止个顶点为止)。顶点顶点v v加入到生成树的顶点集合加入到生成树的顶点集合V(T)V(T)中,中,V(T)V(T)TKSTKS5 57:42(2)(2)算法步骤算法步骤(构造过程构造过程)假设假设N=(VN=(V,E)E)是连通网,是连通网,TETE是是N N上最小生成树中边的集合。上最小生成树中边的集合。U=u0(u0V)U=u0(u0V),TE=TE=。在所有在所有uUuU,vVvV-U-U的边的边(

    5、u(u,v)Ev)E中找一条权值最小的边中找一条权值最小的边(u0(u0,v0)v0)并入集合并入集合TETE,同时,同时v0v0并入并入U U。重复重复,直至,直至U=VU=V为止。为止。此时此时TETE中必有中必有n-ln-l条边,则条边,则T=(VT=(V,TE)TE)为为N N的最小生成树。的最小生成树。示例示例1 1:v v1 1v v2 2v v3 3v v4 4v v5 5v v6 63 35 55 52 24 46 61 15 56 66 6 v v5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 v v1 1v v2 2v v3 3v v4 4v

    6、v5 5v v6 610105 56 66 66 610107 7121210101515 v v5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 示例示例2 2:TKSTKS6 67:42(3)(3)普里姆算法的实现普里姆算法的实现 邻接矩阵结构邻接矩阵结构 typedef structtypedef struct char vexsmvnum char vexsmvnum;int arcsmvnummvnum int arcsmvnummvnum;int vexnum,arcnum int vexnum,arcnum;amgraph amgraph;记录前驱顶点

    7、和记录前驱顶点和V(T)V(T)中到中到V-V-V(T)V(T)权值最小的边的存储空间权值最小的边的存储空间structstruct int adjvex int adjvex;int lowcostint lowcost;closedgenvnum closedgenvnum;算法实现算法实现 初始化:初始化:首先将初始顶点甜加入首先将初始顶点甜加入U U中,对其余的每一个顶点中,对其余的每一个顶点v vi i,将将closedgeiclosedgei 均初始化为到均初始化为到u u的边信息。的边信息。循环循环n-ln-l次,做加下处理:次,做加下处理:a a、从各组最小边从各组最小边clo

    8、sedgevclosedgev 中选出最小的最小边中选出最小的最小边closedgekclosedgek,输出此边输出此边(v(v,k kV V-U)-U);b b、将将k k加入加入U U中;中;c c、更新剩余的每组最小边信息更新剩余的每组最小边信息closedgevclosedgev,(v(vV V-U)-U)。TKSTKS7 77:42 v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56 66 66 610107 7121210101515lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex

    9、 lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex k k V-T(V)V-T(V)T(V)T(V)V V6 6V V5 5V V4 4V V3 3V V2 2 V V closedgeclosedge v v5 5 v v1 1 1 1 V V2 2V V3 3V V4 4V V5 5V V6 6 VV1 1 121215151010V V1 1V V1 1V V1 1 2 2 V V3 3V V4 4V V5 5V V

    10、6 6 VV1 1V V2 2 V V2 2V V1 1V V2 2V V2 2 v v2 2 7 715156 65 50 03 3 v v3 3 V V4 4V V5 5V V6 6 VV1 1V V2 2V V3 3 7 715156 60 00 0V V2 2V V1 1V V2 24 4 v v4 4 V V5 5V V6 6 VV1 1V V2 2V V3 3V V4 4 6 610100 00 00 0V V4 4V V4 46 6 v v6 6 V V5 5 VV1 1V V2 2V V3 3V V4 4V V6 6 0 010100 00 00 0V V4 45 5 VV1

    11、1V V2 2V V3 3V V4 4V V6 6V V5 5 0 00 00 00 00 0 示例示例v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56 66 66 610107 7121210101515 生成树可生成树可能不唯一能不唯一TKSTKS8 87:42 算法描述算法描述void minispantree_prim(amgraph g,charvoid minispantree_prim(amgraph g,char u)u)/普里姆算法普里姆算法 struct struct int adjvex int adjvex;int lowcost

    12、 int lowcost;closedgemvnum closedgemvnum;int i,j,k,min int i,j,k,min;k=locatevex(g,u,g.vexnum k=locatevex(g,u,g.vexnum););/初始化初始化 for(j=0;jg.vexnum;jfor(j=0;jg.vexnum;j+)+)if(j if(j!=k)!=k)closedgej.adjvex closedgej.adjvex=k;=k;closedgej.lowcost=g.arcskj closedgej.lowcost=g.arcskj;closedgek.lowcost

    13、closedgek.lowcost=0;=0;TKSTKS9 97:42 for(i=1;ig.vexnum;i for(i=1;ig.vexnum;i+)+)/重复重复n-1n-1次做次做 min=maxint min=maxint;for(j=0;jg.vexnum;j for(j=0;j0&closedgej.lowcost0&closedgej.lowcost%c ,g.vexsclosedgek.adjvex printf(%c-%2d-%c ,g.vexsclosedgek.adjvex,closedgek.lowcost,g.vexsk closedgek.lowcost,g.v

    14、exsk););/输出输出 closedgek.lowcostclosedgek.lowcost=0;=0;/把顶点把顶点vexskvexsk 加入到加入到T T for(j=0;jg.vexnum;j for(j=0;jg.vexnum;j+)+)/调整调整if(g.arcskjclosedgej.lowcostif(g.arcskjclosedgej.lowcost)closedgej.adjvex closedgej.adjvex=k;=k;closedgej.lowcost=g.arcskj closedgej.lowcost=g.arcskj;getchgetch();();TKST

    15、KS 10107:42 算法分析算法分析 时间复杂度:时间复杂度:4 4、克鲁斯卡尔算法克鲁斯卡尔算法(1)(1)克鲁斯卡尔算法的构造过程克鲁斯卡尔算法的构造过程 10101110)1()1()1(njnjninjOOO)()1()1)(12()1(2)1(21011nOOnnOnOnjniTKSTKS 11117:42 即即(算法步骤算法步骤)(2)(2)示例示例v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56 66 66 610107 7121210101515v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56

    16、66 66 610107 71212101015155 56 66 610101010 生成树可能生成树可能不唯一不唯一TKSTKS 12127:42(3)(3)克鲁斯卡尔算法的实现克鲁斯卡尔算法的实现 辅助数据结构辅助数据结构 存储边信息的结构体存储边信息的结构体(数组数组 edge)edge)struct edgenode struct edgenode int int head;/head;/边的始点边的始点 intint tail;/tail;/边的终点边的终点 int lowcostint lowcost;/;/边上的权值边上的权值 ;标识各顶点连通分量数组标识各顶点连通分量数组 v

    17、exsetarcnumvexsetarcnum 对每个顶点对每个顶点viVviV,对应元素,对应元素vexsetivexseti 表示该顶点所在的连通表示该顶点所在的连通分量。初始时:分量。初始时:vexsetivexseti=i=i,表示各顶点自成一个连通分量。表示各顶点自成一个连通分量。TKSTKS 13137:42 算法思想算法思想 将边信息数组将边信息数组edgeedge中的元素按权值从小到大排序。中的元素按权值从小到大排序。依次从排好序的数组依次从排好序的数组edgeedge中选出一条边中选出一条边(v(vl l,v v2 2),在,在vexsetvexset中中分别查找分别查找v

    18、vl l和和v v2 2所在的连通分量所在的连通分量VSVS1 1和和VSVS2 2。若若VSVS1 1和和VSVS2 2不等,表明所选的两个顶点分属不同的连通分量,不等,表明所选的两个顶点分属不同的连通分量,输出此边,并合并输出此边,并合并VSVS1 1和和VSVS2 2两个连通分量;两个连通分量;若若VSVS1 1和和VSVS2 2 相等,表明所选的两个顶点属于同一个连通分量,相等,表明所选的两个顶点属于同一个连通分量,舍去此边而选择下一条权值最小的边。舍去此边而选择下一条权值最小的边。重复重复(n-1(n-1次次),直至,直至edgeedge中所有的边都扫描判断完,并且所中所有的边都扫描

    19、判断完,并且所有顶点都在同一连通分量上。有顶点都在同一连通分量上。算法描述算法描述void minispantree_kruskal(amgraphvoid minispantree_kruskal(amgraph g)g)int i,j,v1,v2,vs1,vs2,int i,j,v1,v2,vs1,vs2,*vexsetvexset;vexset=new intg.vexnum vexset=new intg.vexnum;TKSTKS 14147:42 sort(g sort(g););for(i=0;ig.vexnum;i+)vexseti for(i=0;ig.vexnum;i+)v

    20、exseti=i;=i;for(i=0;ig.arcnum;i for(i=0;i%c ,g.vexsv1,printf(%c-%2d-%c ,g.vexsv1,g.edgei.lowcost,g.vexsv2);g.edgei.lowcost,g.vexsv2);for(j=0;jg.vexnum;jfor(j=0;jg.vexnum;j+)+)if(vexsetj=vs2)vexsetj if(vexsetj=vs2)vexsetj=vs1;=vs1;TKSTKS 15157:42 算法分析算法分析 时间复杂度:时间复杂度:(n(ne)e)(e(elogeloge)(4)(4)比较两种算法比较比较两种算法比较 算法名算法名 普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度 (n(n2 2)(n(ne)e)适应范围适应范围 稠密图稠密图 稀疏图稀疏图?1 1、书面作业:、书面作业:P161P161:2 2中中(1)(1)、(2)(2)、(3)(3)2 2、实践:、实践:实验二、栈序列匹配实验二、栈序列匹配TKSTKS 16167:42

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:第十五讲图3数据结构绍兴文理学院课件.ppt
    链接地址:https://www.163wenku.com/p-5070556.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库