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

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