分享
分销 收藏 举报 申诉 / 44

类型数据结构第七章图(4).ppt

  • 上传人:仙人****88
  • 文档编号:14770688
  • 上传时间:2026-11-18
  • 格式:PPT
  • 页数:44
  • 大小:775.50KB
  • 下载积分:10 金币
  • 配套讲稿:

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

    特殊限制:

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

    关 键  词:
    数据结构 第七
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四节 图的连通性问题,一、无向图的连通分量和生成树,1,、无向图的连通分量,连通分量(,Connected Components,),无向图的连通分量,We can use the two elementary graph searchs,to create additional,,,more interesting,,,graph,operations.,For illustrative purposes,,,let us look at the,problem of determining whether or not an,undirected graph is connected.,无向图的连通分量,We can implement this operation by simply,calling either DFS,(,0,),or BFS,(,0,),and then,determining if there are any unvisited vertices.,无向图的连通分量,在对无向图进行遍历时,对于连通图,仅需从图,中任一顶点出发,进行深度优先搜索或宽度优先,搜索,便可访问到图中的所有顶点,对于非连通图,则需要从多个顶点出发进行搜索,,而每一次从一个新的起始点出发进行搜索过程中,得到的顶点访问顺序恰恰为其各个连通分量中的,顶点集,无向图的连通分量,例如:图,7.3,中的,G3,是非连通图,按照图,7.14,中,所示的邻接链表进行深度优先搜索,三次调用,DFS,过程,这三个顶点集分别加上所有依附于这下顶点的边,,便构成了非连通图,G3,的三个连通分量,2,、生成树(,Spanning Trees,),A spanning tree is any tree that consists solely of,edges in G and that includes all the vertices in G.,一个连通图的生成树是一个极小连通子图,它,含有图中全部顶点,但只有足以构成一棵树的,n-1,条边,生成树,When graph G is connected,,,a depth first search,or breadth first search starting at any vertex,visits all the vertices in G.,The search implicitly partitions the edges in G,into two sets,:,T,(,for tree edges,),and N,(,for,nontree edges,),.,生成树,T is the set of edges used or traversed during the,search and N is the set of remaining edges.,The edges in T form a tree that includes all vertices,of G.,生成树,As we just indicated,,,we may use either dfs or bfs,to create a spanning tree.,When dfs is used,,,the resulting spanning tree is,known as a,depth first spanning tree,.,When bfs is used,,,the resulting spanning tree is,known as a,breadth first spanning tree,.,二、最小生成树,Minimum cost spanning tree,也称为最小代价生成树,最小代价生成树,The cost of a spanning tree of a weighted undireted,graph is the sum of the costs,(,i.e.weights,),of the,edges in the spanning tree.,A minimum cost spanning tree of least cost.,最小代价生成树,There are three different algorithms can be used,to obtain a minimum cost spanning tree of a,connected undirected graph.,All three use an algorithms design strategy called,the greedy method,(,贪婪算法),.,最小代价生成树,We shall refer to the three algorithms as,:,Kruskals algorithm,Prims algorithm,Sollins algorithm,最小代价生成树,In the greed method,,,we construct an optimal,(,最优的),solution in stages.,At each stages,,,we make a decision that is the,best decision,(,using some criterion,),at this time.,Since we cannot change this decision later,,,we,make sure that the decision will reach in a feasible,solution.,最小代价生成树,The greedy method can be applied to a wide,variety of programming problems.,Typically,,,the selection of an item at each stage,is based on either a least cost or a highest profit,criterion.,Prims algorithm,Prims algorithm,like Kruskals,constructs,the minimum cost spanning tree one stage at,one time.,However,at each stage of the algorithm,,the,set of selected edges forms a tree,,by contrast,,the set of selected edges in Kruskals algorithm,forms a forest at each stage,.,Prims algorithm,Prims algorithm begins with a tree,T,that,contains a single vertex.,This may be any of the vertices in the original,graph.,Prims algorithm,Next,we add a least cost edges(u,v)to T,so that T(u,v)is also a tree.,We repeat this edge addition step until T contains,n-1 edges.,Prims algorithm,To make sure that the added edge does not from a,cycle,,,at each step we choose the edge,(,u,,,v,),such that exactly one of u or v is inT.,典例分析,T=;,TV=0;/start with vertex 0 and no edges,while T contains fewer than n-1 edges,let u,v be a least cost edge such that,uTV and v not TV;,if there is no such edge,break;,add v to TV;,add u,v to T;,if T contains fewer than n-1 edges,printf(”No spanning treen”);,第五节 有向无环图及其应用,一、有向无环图(,directed acycline graph,,,DAG,),一个无环的有向图称为有向无环图,简称,DAG,图,有向无环图,DAG,图是一类较有向图更一般的特殊有向图,P179,图,7.21,:显示了有向树、,DAG,图和有向图,的区别,有向无环图,DAG,图是描述含有公共子式的表达式的有效工具,P179,典例分析,若,利用,DAG,图,则可实现对相同子式的共享,,从而节省存储空间,有向无环图,检查一个有向图是否存在环比无向图要复杂,对于无环图来说,若深度优先遍历过程中遇到,回边(即指向已访问过的顶点的边),则肯定,存在环,二、拓扑排序(,Topological Sort,),A topological order is a linear ordering of the,vertices of a directed graph,拓扑排序,拓扑排序的算法,在有向图中选择一个没有前驱的顶点且输出之,从图中删除该顶点和所有以它为尾的弧,拓扑排序,重复上述两步,直到全部顶点均已全部输出,,或者当前图中不存在无前驱的顶点为止,后一种情况则说明有向图中肯定存在环,拓扑排序,拓扑排序的详细算法,以邻接表作为存储结构,把邻接表中所有入度为,0,的顶点进栈,拓扑排序,栈非空时,输出栈顶元素,Vj,并退栈,在邻接表中查找,Vj,的直接后继,Vk,,,把,Vk,的入度,减1,若,Vk,的入度为0则进栈,拓扑排序,重复上述操作直至栈空为止,若栈空时输出的顶点个数不是,n,,,则有向图有环,否则,拓扑排序完毕,0,1,2,2,in,link,5,5,4,3,vex,next,3,2,5,2,4,0,1,2,3,4,5,6,1,2,3,4,5,6,邻接表结点,typedef struct node,int adjvex,;,/,顶点域,struct node *nextarc,;,/,链域,JD,;,表头结点,typedef struct node,int in,;,/,入度域,struct node *link,;,/,链域,TD,;,TD gM,;,/g0,不用,Status TopologicalSort,(,ALGraph G,),/,有向图,G,采用邻接表存储结构,/,若,G,无回路,则输出,G,的顶点的一个拓扑排序序列,并返回,OK,;,否则,ERROR,;,FindInDegree,(,G,,,indegree,);,InitStack,(,S,);,for,(,i=0,;,inextarc,),/,对,i,号顶点的每个邻接点的入度减,1,k=p-adjvex,;,if,(,!,(,-indegreek,),Push,(,S,,,k,);,/,若入度减为,0,,则入栈,/for,if,(,countG.vernum,),return ERROR,;,/,该有向图有回路,else,return OK,;,/TopologicalSort,
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:数据结构第七章图(4).ppt
    链接地址:https://www.zixin.com.cn/doc/14770688.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork