有向图及无向图的比较研究.ppt

《有向图及无向图的比较研究.ppt》由会员分享，可在线阅读，更多相关《有向图及无向图的比较研究.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、有向图及无向图的比较研究知识结构图的定义无向图与有向图无向图与有向图异同点图图（图（GraphGraph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间描述元素之间“多对多”的关系。的关系。一一 图的定义图的定义 图图G G由两个集合构成，记作由两个集合构成，记作G=(V,E)G=(V,E)其中其中V V是顶点的非空有限集是顶点的非空有限集合，合，E E是边的有限集合，其中边是顶点的无序对或有序对集合。是边的有限集合，其中边是顶点的无序对或有序对集合。G1=(V1,E1)G1=(V1,E1)V1=vV1=v0 0,v,v1 1,v,v2 2

2、,v,v3 3,v,v4 4 E1=(vE1=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v2 2,v,v3 3)(v)(v2 2,v,v4 4)无序对无序对(v(vi i,v,vj j)：用连接顶点用连接顶点v vi i、v vj j的线段的线段表示，称为表示，称为无向边无向边；V0V0 V4V4 V3V3 V1V1 V2V2例例G1 G1 图示图示G2 G2 图示图示有序对有序对v ：用以为用以为v vi i起点、以起点、以v vj j为终点为终点的有向线段表示，称为的有向线段表示，称为有

3、向有向边或弧；边或弧；V0V0 V1V1 V2V2 V3V3G2=G2=V2=vV2=v0 0 v v1 1,v,v2 2,v,v3 3 E2=vE2=,v,有向有向图和无向和无向图在在图图中中，若若用用箭箭头头标标明明了了边边是是有有方方向向性性的的，则则称称这这样样的图为有向图，否则称为无向图。的图为有向图，否则称为无向图。在在无无向向图图中中，一一条条边边（x,y）与与（y,x）表表示示的的结结果果相相同同，用用圆圆括括号号表表示示，在在有有向向图图中中，一一条条边边与与表表示示的的结结果果不不相相同同，故故用用尖尖括括号号表表示示。表表示从顶点示从顶点x发向顶点发向顶点y的边，的边，x

4、为始点，为始点，y为终点。为终点。V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3有向图：有向图：无向图：无向图：完全图完全图:图G中的每条中的每条边都是有方向的；都是有方向的；图G中的每条中的每条边都是无方向的；都是无方向的；图G任意两个任意两个顶点都有一条点都有一条边相相连接；接；若若 n 个个顶点的无向点的无向图有有 n(n-1)/2 条条边,称称为无向完全无向完全图若若 n 个个顶点的有向点的有向图有有n(n-1)条条边,称称为有有向完全向完全图图的应用举例：图的应用举例：例例1 1 交通图（公路、铁路）交通图（公路、铁路）顶点：地点顶点：地点

5、边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向交通图中的有单行道双行道，分别用有向边、无向边表示；边表示；例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地点间的连线例例4 4 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3异同点证明：明：若是完全有向若是完全有向图

6、，则n个个顶点中点中的每个的每个顶点都有一条弧指向其它点都有一条弧指向其它n-1个个顶点点,因此因此总边数数=n(n-1)证明：明：从从可以直接推可以直接推论出无向完全出无向完全图的的边数数因因为无方向，两弧合并无方向，两弧合并为一一边，所以所以边数减半，数减半，总边数数为n(n-1)/2。完全无向完全无向完全无向完全无向图图有有有有n n(n n-1)/2-1)/2 条条条条边边。完全有向完全有向完全有向完全有向图图有有有有n n(n n-1)-1)条条条条边边。12341234 图的的邻接表表示接表表示 图的邻接表存储方法是一种顺序分配与链式分配相结合图的邻接表存储方法是一种顺序分配与链式

7、分配相结合的存储方法，它包括两部分的存储方法，它包括两部分：边表和顶点表。：边表和顶点表。边表是单链表，用来存放边的信息；边表是单链表，用来存放边的信息；顶点表是数组，主要用来存放顶点本身的数据信息和顶点表是数组，主要用来存放顶点本身的数据信息和该顶点邻接点的位置。该顶点邻接点的位置。adjvex weight next 边结点边结点顶点结点顶点结点1 1 无向图的邻接表无向图的邻接表顶点：通常按编号顺序将顶点数据存顶点：通常按编号顺序将顶点数据存储在一维数组中；储在一维数组中；关联同一顶点的边：用线性链表存储关联同一顶点的边：用线性链表存储该结点表示边该结点表示边（Vi VjVi Vj）,其

8、中的其中的1 1是是VjVj在一维数组中的位置在一维数组中的位置例例 V0V0 V4V4 V3V3 V1V1 V2V22 2 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 03 34 4下下标 编号号 link2 2 有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表1 1）有向图的邻接表）有向图的邻接表顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储以同一顶点为起点的弧：用线性链表存储类似于无向图的邻接表，类似于无向图的邻接表，所不同的是：所不

9、同的是：以同一顶点为起点的弧：以同一顶点为起点的弧：用线性链表存储用线性链表存储下标下标 编号编号 link link V0V0V1V1V2V2V3V31 12 23 30 0 0 1 2 3m-1例例 V0V0 V1V1 V2V2 V3V32 2）有向图的逆邻接表）有向图的逆邻接表顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储以同一顶点为终点的弧：用线性链表存储V0V0V1V1V2V2V3V3 0 1 2 3m-10 00 02 23 3 类似于有向图的邻接表，类似于有向图的邻接表，所不同的是：所不同的是：以同一顶点为终点弧：以同一顶

10、点为终点弧：用线性链表存储用线性链表存储例例 V0V0 V1V1 V2V2 V3V32 从无向从无向图的的邻接表可以得到如下接表可以得到如下结论 1 1）在）在G G邻接表中，同一条边对应两个结点，邻接表中，同一条边对应两个结点，所有链表中结所有链表中结点数目的一半为图中边数；点数目的一半为图中边数；2）顶点）顶点v的度：等于的度：等于v对应线性链表的长度；对应线性链表的长度；3）判定两顶点）判定两顶点v v，u u是否邻接：要看是否邻接：要看v v对应线性链表中有对应线性链表中有无对应的结点无对应的结点 4 4）在）在G G中增减边：要在两个单链表插入、删除结点；中增减边：要在两个单链表插入

11、、删除结点；5 5）设存储顶点的一维数组大小为）设存储顶点的一维数组大小为m(mm(m 图的顶点数图的顶点数n),n),图图的边数为的边数为e e，G G占用存储空间为：占用存储空间为：m+2*em+2*e。G G占用存储空间与占用存储空间与 G G 的顶点数、边数均有关；的顶点数、边数均有关；3 从有向从有向图的的邻接表可以得到如下接表可以得到如下结论（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。

12、为此，从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。个顶点的入度。适用于边稀疏的图适用于边稀疏的图邻接矩阵：邻接矩阵：A.Edge=（v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0分析分析分析分析1 1：无向无向无向无向图图的的的的邻邻接矩接矩接矩接矩阵阵是是是是对对称称称称的；的；的；的；分析分析分析分析2 2：顶顶点点点点V Vi i 的的的的度度度度第第第第 i i 行行行行(列列列列)

13、中中中中1 1 的个数的个数的个数的个数；特特特特别别：完全完全完全完全图图的的的的邻邻接矩接矩接矩接矩阵阵中，中，中，中，对对角元素角元素角元素角元素为为0 0，其余全，其余全，其余全，其余全1 1。顶点表：顶点表：无向图的邻接矩阵如何表示？无向图的邻接矩阵如何表示？v1v2v3v5v4v4A A0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0有向图的邻接矩阵如何表示？有向图的邻接矩阵如何表示？分析分析分析分析1 1：有向有向图的的邻接矩接矩阵可能是不可能是不对

14、称称的。的。分析分析分析分析2 2：顶点点vi的的出度出度=第第i行元素之和行元素之和，OD(vi)=A.Edge i j 顶点点vi的的入度入度=第第i列元素之和列元素之和。ID(vi)=A.Edge j i 顶点的点的度度=第第i行元素之和行元素之和+第第i列元素之和列元素之和,即：即：TD(vi)=OD(vi)+ID(vi)v1v2v3v4A A邻接矩阵：邻接矩阵：A.Edge=(v1 v2 v3 v4)v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：注：注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i行含行含义：以：以结点点vi为尾的弧尾的弧(即即vi出度出度边）；）；第第i列含列含义：以：以结点点vi为头的弧的弧(即即vi入度入度边）。）。顶点表：顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 谢谢欣赏