资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：刘斌,图的基本概念,常州信息职业技术学院,02,教,学,目标,1,2,3,图（,Graph,）的二元组定义,03,图的基本概念,图的边和顶点的关系,三、链表的插入,04,图的基本概念,0.1,1,、,图的概念,图是一种复杂的非线性结构，在图结构中，对结点的前驱和后继的个数没有任何限制，,结点之间的关系是任意的，图中任意两个结点之间都可能有关系,。图结构在计算机科学、人工智能、工程、数学、物理等领域中，有着广泛的应用。,05,图的基本概念,0.1,1,图（,Graph,）,的二元组定义,图,G,由两个集合,V,和,E,组成，记为：,G=(V,E),其中，,V,是有限的非空集合，,V,中的元素称为,顶点（,Vertex,）,或结点，,E,是,V,中顶点偶对,(vi,vj),的集合，,E,中的元素称为,边（,Edge,）,。,说明,：,图,G,的顶点集和边集也可记为,V(G),和,E(G),。,E(G),可以是空集，若为空，则图,G,只有顶点没有边；图中的边,(vi,vj),描述了两个顶点之间是相关的。,06,图的基本概念,0.1,在图,5-1,中的,图,G1,：,V1,V2,V3,V4,V5,图,5-1,图,G1,G1=(V,E),，,顶点集合,V=v1,v2,v3,v4,v5,，,边集合,E,(v1,v2),(v1,v4),(v2,v3), (v2,v5),(v3,v4),(v3,v5) ,。,07,图的基本概念,0.1,2,无向图和有向图,若图,G,中的每条边都是没有方向的，则称,G,为无向图。,无向图中边的表示：无向图中的边均是顶点的无序对，无序对通常用圆括号表示，无序对,(vi,vj),和,(vj,vi),表示图中的同一条边。如图,5-1,所示图,G1,是一个无向图。,V1,V2,V3,V4,V5,图,5-1,图,G1,（,1,）无向图（,Undir,ected Graph,）,08,图的基本概念,0.1,（,2,）有向图（,Dire,cted Graph,）,若图,G,中的每条边都是有方向的，则称,G,为有向图。,有向图中边的表示：有向图中的边是由顶点的有序对组成，有序对通常用尖括号表示，有序对,和,表示的是图中不同的边。有向边,也称为弧，边的始点,vi,称为弧尾，终点,vj,称为弧头。,图,5-2,图,G2,V1,V2,V3,V4,09,图的基本概念,0.1,1,2,（,3,）完全图（,Complete Graph,）,无向完全图：若,G,是具有,n,个顶点,e,条边的无向图，则顶点数与边数的关系为,0en(n-1)/2,。把恰有,n(n-1)/2,条边的无向图称为无向完全图。,有向完全图：若,G,是具有,n,个顶点,e,条边的有向图，则顶点数与边数的关系为,0en(n-1),。把恰有,n(n-1),条边的有向图称为有向完全图。,说明,：,完全图具有最多的边数。任意一对顶点间均有边相连。,09,图的基本概念,0.1,（,4,）稀疏图（,Sparse Graph,）和稠密图（,Dense Graph,）,如果一个图的边数很少，则称该图为稀疏图，否则称为稠密图。比如含有,n,个顶点的图,G,，,G,的边数,enlgn,，可认为图,G,为稀疏图,稀疏图,稠密图,10,图的基本概念,0.1,1,2,3,图的边和顶点的关系,（,1,）无向边和顶点关系,若,(vi,vj),是一条无向边，则称顶点,vi,和,vj,互为邻接顶点，或称,vi,和,vj,相邻接；并称,(vi,vj),依附或关联于顶点,vi,和,vj,，或称,(vi,vj),与顶点,vi,和,vj,相关联。,（,2,）有向边和顶点关系,若,是一条有向边，则称顶点,vi,邻接到顶点,vj,，顶点,vj,邻接于顶点,vi,；并称边,关联于,vi,和,vj,，或称,与顶点,vi,和,vj,相关联,11,图的基本概念,0.1,（,3,）顶点的度,1,2,4,5,3,无向图中顶点,v,的度：无向图中顶点,v,的度是关联于该顶点的边的数目，记为,D(v),有向图顶点,v,的入度：有向图中，以顶点,v,为终点的边的数目称为,v,的入度，记为,ID(v),。,有向图顶点,v,的出度：有向图中，以顶点,v,为始点的边的数目，称为,v,的出度，记为,OD(v),有向图顶点,v,的度：有向图中，顶点,v,的度定义为该顶点的入度与出度之和，即,D(v)=ID(v)+OD(v),。,无论有向图还是无向图，顶点数,n,、边数,e,和度数之间有如下关系：,12,图的基本概念,0.1,V1,V2,V3,V4,V5,图,5-1,图,G1,图,5-2,图,G2,V1,V2,V3,V4,在图,5-1,无向图,G1,中有：,D(v1)=2,，,D(v2)=3,，,D(v3)=3,，,D(v4)=2,，,D(v5)=2,。,在图,5-2,有向图,G2,中有：,ID(v1)=1,，,OD(v1)=2,，,D(v1)=3,；,ID(v2)=1,，,OD(v2)=0,，,D(v2)=1,；,ID(v3)=1,，,OD(v3)=1,，,D(v3)=2,；,ID(v4)=1,，,OD(v4)=1,，,D(v4)=2,。,13,图的基本概念,0.1,设,G=(V,E),是一个图，若,V,是,V,的子集，,E,是,E,的子集，且,E,中的边所关联的顶点均在,V,中，则,G=(V,E),也是一个图，并称其为,G,的子图。,4,子图（,SubGraph,）,V1,V2,V3,V4,V5,图,5-1,图,G1,图,5-2,图,G2,V1,V2,V3,V4,V1,V2,V3,V4,V5,图,5-3,图,G1,和图,G2,的子图,V1,V3,V4,三、链表的插入,14,图的基本概念,0.1,1,3,2,5,路径,（,1,）无向图的路径,在无向图,G,中，若存在一个顶点序列,v,p,，,v,i1,，,v,i2,，,，,v,im,，,v,q,，使得,(v,p,v,i1,),，,(v,i1,v,i2,),，,，,(v,im,v,q,),均属于,E(G),，则称该序列为顶点,v,p,到,v,q,的一条路径。,（,2,）有向图的路径,在有向图,G,中，若存在一个顶点序列,v,p,，,v,i1,，,v,i2,，,，,v,im,，,v,q,，使得有向边,，,，,，,均属于,E(G),，则称该序列为顶点,v,p,到,v,q,的一条路径。,（,3,）路径长度,路径长度定义为该路径上边的数目。,15,图的基本概念,0.1,4,6,5,（,4,）简单路径,若一条路径除两端顶点可以相同外，其余顶点均不相同，则称此路径为一条简单路径,（,5,）回路,起点和终点相同的路径称为回路。,（,6,）简单回路或简单环,起点和终点相同的简单路径称为简单回路或简单环。,16,图的基本概念,0.1,6,连通图和连通分量,（,1,）顶点间的连通性,在无向图,G,中，若从顶点,vi,到顶点,vj,有路径，则称,vi,和,vj,是连通的。,（,2,）连通图（,Connected Graph,）,若在无向图,G,中，任意两个不同的顶点,vi,和,vj,都连通（即有路径），则称图,G,为连通图。,（,3,）连通分量（,Connected Component,）,无向图,G,的极大连通子图称为,G,的,连通分量,。,16,图的基本概念,0.1,示例,(a,）无向图,G3,A,B,D,E,F,C,A,B,E,F,D,C,(b,）图,G3,的两个连通分量,图,5-4,图,G3,及其连通分量,17,图的基本概念,0.1,7,、,网络（,Net,work,）,若将图的每条边都赋上一个权，则称这种带权图为网络。,说明,：,权是表示两个顶点之间的距离、耗费等具有某种意义的数。,示例：如图,5-6,的图,G4,是一个无向网络。,A,B,C,D,图,5-6,无向网络,G4,5,8,1,7,5,THANKS,2016.9.18,
展开阅读全文