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