有向图及无向图的比较研究PPT课件_第1页
有向图及无向图的比较研究PPT课件_第2页
有向图及无向图的比较研究PPT课件_第3页
有向图及无向图的比较研究PPT课件_第4页
有向图及无向图的比较研究PPT课件_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

有向图及无向图的比较研究,.,2,知识结构,图的定义无向图与有向图无向图与有向图异同点,.,3,图,图(Graph)是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构,用来描述元素之间“多对多”的关系。,.,4,一图的定义图G由两个集合构成,记作G=(V,E)其中V是顶点的非空有限集合,E是边的有限集合,其中边是顶点的无序对或有序对集合。,G1=(V1,E1)V1=v0,v1,v2,v3,v4E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4),无序对(vi,vj):用连接顶点vi、vj的线段表示,称为无向边;,例,G1图示,.,5,G2图示,有序对:用以为vi起点、以vj为终点的有向线段表示,称为有向边或弧;,G2=V2=v0v1,v2,v3E2=,.,6,有向图和无向图,在图中,若用箭头标明了边是有方向性的,则称这样的图为有向图,否则称为无向图。在无向图中,一条边(x,y)与(y,x)表示的结果相同,用圆括号表示,在有向图中,一条边与表示的结果不相同,故用尖括号表示。表示从顶点x发向顶点y的边,x为始点,y为终点。,.,7,有向图:无向图:完全图:,图G中的每条边都是有方向的;图G中的每条边都是无方向的;图G任意两个顶点都有一条边相连接;,若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图,.,8,图的应用举例:例1交通图(公路、铁路)顶点:地点边:连接地点的公路交通图中的有单行道双行道,分别用有向边、无向边表示;例2电路图顶点:元件边:连接元件之间的线路例3通讯线路图顶点:地点边:地点间的连线例4各种流程图如产品的生产流程图顶点:工序边:各道工序之间的顺序关系,.,9,异同点,证明:若是完全有向图,则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1),证明:从可以直接推论出无向完全图的边数因为无方向,两弧合并为一边,所以边数减半,总边数为n(n-1)/2。,完全无向图有n(n-1)/2条边。,完全有向图有n(n-1)条边。,.,10,图的邻接表表示,图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法,它包括两部分:边表和顶点表。边表是单链表,用来存放边的信息;顶点表是数组,主要用来存放顶点本身的数据信息和该顶点邻接点的位置。,边结点,顶点结点,.,11,1无向图的邻接表顶点:通常按编号顺序将顶点数据存储在一维数组中;关联同一顶点的边:用线性链表存储,该结点表示边(ViVj),其中的1是Vj在一维数组中的位置,例,下标编号link,.,12,2有向图的邻接表和逆邻接表1)有向图的邻接表顶点:用一维数组存储(按编号顺序)以同一顶点为起点的弧:用线性链表存储,类似于无向图的邻接表,所不同的是:以同一顶点为起点的弧:用线性链表存储,例,.,13,2)有向图的逆邻接表顶点:用一维数组存储(按编号顺序)以同一顶点为终点的弧:用线性链表存储,类似于有向图的邻接表,所不同的是:以同一顶点为终点弧:用线性链表存储,例,.,14,2从无向图的邻接表可以得到如下结论,1)在G邻接表中,同一条边对应两个结点,所有链表中结点数目的一半为图中边数;2)顶点v的度:等于v对应线性链表的长度;3)判定两顶点v,u是否邻接:要看v对应线性链表中有无对应的结点4)在G中增减边:要在两个单链表插入、删除结点;5)设存储顶点的一维数组大小为m(m图的顶点数n),图的边数为e,G占用存储空间为:m+2*e。G占用存储空间与G的顶点数、边数均有关;,.,15,3从有向图的邻接表可以得到如下结论,(1)第i个链表中结点数目为顶点i的出度;(2)所有链表中结点数目为图中弧数;(3)占用的存储单元数目为n+e。,从有向图的邻接表可知,不能求出顶点的入度。为此,我们必须另外建立有向图的逆邻接表,以便求出每一个顶点的入度。,适用于边稀疏的图,.,16,邻接矩阵:,A.Edge=,(v1v2v3v4v5),v1v2v3v4v5,0101010101010111010101110,分析1:无向图的邻接矩阵是对称的;分析2:顶点Vi的度第i行(列)中1的个数;特别:完全图的邻接矩阵中,对角元素为0,其余全1。,顶点表:,无向图的邻接矩阵如何表示?,0000000000000000000000000,0101010101010111010101110,.,17,有向图的邻接矩阵如何表示?,分析1:有向图的邻接矩阵可能是不对称的。分析2:顶点vi的出度=第i行元素之和,OD(vi)=A.Edgeij顶点vi的入度=第i列元素之和。ID(vi)=A.Edgeji顶点的度=第i行元素之和+第i列元素之和,即:TD(vi)=OD(vi)+ID(vi),邻接矩阵:,A.Edge=,(v1v2v3v4),v1v2v3v4,0000000000000000,注:在

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论