ch7图new.ppt

《ch7图new.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图8/15/202111.1数据结构讨论的范畴例1.3铺设煤气管道问题ADCFEB7131791812752410怎样铺设管道最省钱（图）3图的最小生成树8/15/202127.1图的定义和基本术语图(Graph)G是由两个集合V和E组成的,表示为G=（V，E）V：有限非空的顶点集合(顶点vertex)—数据元素E：由所有两个顶点对之间的弧（边）组成的集合（边Edge）—数据关系ADEFCB通常可以根据图的顶点对将图分为有向图和无向图。8/15/20213弧和有向图如下图(a)是一个有向图G，可形式地表示为：

2、G=(V,E)V={a，b，c，d，e}E={，，，，，，，}E是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头bcdea（a)有向图G8/15/20214边和无向图如图(b)所示的是一个无向图G，可形式地表示为：G=(V,E)V={a，b，c，d}E={(a,b),(a,c),(a,d),(b,d),(c,d)}E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（

3、v,w)=(w,v)bcda(b)无向图G8/15/20215权——与图的边或弧相关的数叫权网——带权的图叫网一个带权有向图12613819552431权与网8/15/20216子图——如果图G(V,E)和图G‘(V’,E‘),满足：V’VE’E则称G‘为G的子图，即取图的一部分或全部的顶点和边（弧）构成的图称为子图。356例245136图与子图子图8/15/20217有向完全图——n个顶点的有向图最大弧数是n(n-1)无向完全图——n个顶点的无向图最大边数是n(n-1)/2例213213有向完全图无向完全图若

4、边或弧的个数e

5、…Vin}，满足(Vij-1,Vij)E或E,(1

6、图中任意两个顶点都是连通的叫~强连通图——有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~强连通图356例连通图例245136连通图8/15/202111非连通图——图中只要有两个顶点不是连通的叫~（强）连通分量——非连通图的每一个极大连通子图叫~非连通图和（强）连通分量例2451368/15/202112生成树和生成森林假设一个连通图有n个顶点和e条边，若其中某n-1条边和n个顶点构成一个极小连通子图，则称该极小连通子图为此连通图的生成树。一个连通图可以找到若干个

7、生成树。对于非连通图，各个连通分量的生成树便构成了该非连通图的生成森林。ADCFEB7131791812752410怎样铺设管道最省钱？图的最小生成树8/15/202113图的基本操作(1)CreateGraph(&G,V,VR)：图的创建操作。初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。(2)LocateVex(G,v)：顶点定位函数。初始条件：G已经存在，v是一个顶点。操作结果：返回v在G中的位置，若G中无此顶点，则返回“空”。(3)FirstAdj(G,v)：求第一个邻接

8、点函数。初始条件：G已经存在，v是G中某个顶点。操作结果：返回v的第一个邻接点，若v在G中无邻接点，则返回“空”。(4)NextAdj(G,v,w)：求下一个邻接点函数。初始条件：G已经存在，v是G中某个顶点，w是v的一个邻接点。操作结果：返回v的邻接点中w之后的下一个邻接点，若无下一邻接点，则返回“空”。8/15/202114(5)getVexVal(G,