图(Graph)是一种较线性表和树更为复杂的非线性结构在线

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,图,图（,Graph）,是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。,基本定义和术语,若图,G,中的每条边都是有方向的，则称,G,为,有向图,（,Digraph）。,在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，,v,i,，v,j,表示一条有向边，,v,i,是边的始点（起点），,v,j,是边的终点。因此，,v,i,，v,j,和,v,j,，v,i,是两条不同的有向边。有向边也称为弧（,Arc），,边的始点称为弧尾（,Tail），,终点称为弧头（,Head）。,图,G,由两个集合,V,和,E,组成，记为,G,(V,，,E),，,其中,v,是顶点的有穷非空集合，,E,是,V,中顶点偶对（称为边）的有穷集。通常，也将图,G,的顶点集和边集分别记为,V(G),和,E(G),。,E(G),可以是空集，若,E(G),为空，则图,G,只有顶点而没有边，称为空图。,若,(,v,i,，,v,j,),是一条无向边，则称顶点,v,i,和,v,j,互为,邻接点,(,Adjacent),，,或称,v,i,和,v,j,相邻接；称,(,v,i,，,v,j,),关联,(,Incident),于顶点,v,i,和,v,j,，,或称,(,v,i,，,v,j,),与顶点,v,i,和,v,j,相关联,。如图,7-1,中,G,2,，,与顶点,v,l,相邻接的顶点是,v,2,，,v,3,和,v,4,，,而关联于顶点,v,2,的边是,(,v,l,，,v,2,),，,(v,2,，,v,3,),和,(,v,2,，,v,4,),。,若,v,i,，,v,j,是一条有向边，则称顶点,v,i,邻接到,v,j,顶点,v,j,邻接于顶点,v,i,并称边,v,i,，,v,j,关联于,v,i,和,v,j,或称,v,i,，,v,j,与顶点,v,i,和,v,j,相关联。如图,7-1,中,G,l,，,关联于顶点,v,2,的边是,v,1,，,v,2,，,v,2,，,v,l,和,v,2,v,3,。,无向图中顶点,v,的,度,(,Degree),是关联于该顶点的边的数目，记为,D(v)。,若,G,为有向图，则把以顶点,v,为终点的边的数目，称为,v,的,人度,(1,ndegree,)，,记为,ID(v)；,把以顶点,v,为始点的边的数目，称为,v,的,出度,(,outdegree,)，,记为,OD(v)；,顶点,v,的度则定义为该顶点的入度和出度之和，即,D(v)ID(v),十,OD(v)。,在无向图,G,中，若存在一个顶点序列,v,p,v,i1,v,i2,，,v,in,，,vq,，,使得(,v,p,，,v,il,)，(v,i1,v,i2,)，(,v,in,，,v,q,),均属于,E(G)，,则称顶点,v,p,到,v,q,存在一条,路径,(,Path)。,若,G,是有向图，则路径也是有向的，它由,E(G),中的有向边,v,p,，,v,il,，,v,il,，v,i2,，,v,in,，,v,q,组成。,路径长度,定义为该路径上边的数目。若一条路径上除了,v,p,和,v,q,可以相同外；其余顶点均不相同，则称此路径为一条,简单路径,。起点和终点相同(,v,p,v,q,),的简单路径称为,简单回路,或,简单环,(,Cycle)。,例如，在图,G,2,中顶点序列,v,l,v,2,，v,3,，v,4,是一条从顶点,v,l,到顶点,v,4,的长度为3的简单路径；顶点序列,v,l,v,2,，v,4,，,v,l,，v,3,是一条从顶点,v,l,到顶点,v,3,的长度为4的路径，但不是简单路径；顶点序列,v,l,，v,2,，v,4,，,v,l,是一个长度为3的简单环。在有向图,G,l,中，顶点序列,v,l,，v,2,，,v,l,是一个长度为2的有向简单环。,在一个有向图中，若存在一个顶点,v,，,从该顶点有路径可以到达图中其它所有顶点，则称此有向图为,有根图,，,v,称作图的,根,。,在无向图,G,中，若从顶点,v,i,到顶点,v,j,有路径,(,当然从,v,j,到,v,i,也一定有路径,),，则称,v,i,和,v,j,是,连通,的。若,V(G),中任意两个不同的顶点,v,i,和,v,j,都连通,(,即有路径,),，则称,G,为,连通图,(,Connected Graph),。,例如，图,G,2,和,G,3,是连通图。,无向图,G,的极大连通子图称为,G,的,连通分量,(,connected Component),。,显然，任何连通图的连通分量只有一个，即是其自身，而非连通的无向图有多个连通分量。例如，图,7-4,中的,G,4,是非连通图，它有两个连通分量,H,l,和,H,2,。,在有向图,G,中，若对于,V(G),中任意两个不同的顶点,v,i,和,v,j,，,都存在从,v,i,到,v,j,以及从,v,j,到,v,i,的路径，则称,G,是,强连通图,。有向图,G,的极大强连通子图称为,G,的,强连通分量,。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。例如图7-1中的,G,l,不是强连通图，因为,v,3,到,v,2,没有路径，但它有两个强连通分量，,若将图的每条边都赋上一个权，则称这种带权图为,网络,(,Network)。,通常权是具有某种意义的数.,它们可以表示两个顶点之间的距离，耗费等,图的存储结构,邻接矩阵,(,Adjacency Matrix),是表示顶点之间相邻关系的矩阵。设,G,(V,，,E),是具有,n,个顶点的图，则,G,的邻接矩阵是具有如下性质的,n,阶方阵：,用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：,#,define n 6 /*,图的顶点数*/,#,define e 8 /*,图的边（弧）数*/,typedef,char,vextype,；/*,顶点的数据类型*/,typedef,float,adjtype,；/*,权值类型*/,typedef struct,vextype vexs,n；,adjtype,arcsnn；,graph；,若图中顶点信息是,0,至,n-1,的编号，则仅需令权值为,1,，存储一个邻接矩阵就可以表示图。若是网络，则,adjtype,为权的类型。由于无向图或无向网络的邻接矩阵是对称的，故可采用压缩存储的方法，仅存储下三角阵,(,不包括对角线上的元素,),中的元素即可。显然，邻接矩阵表示法的空间复杂度,S(n),O(n,2,),。,CREATGRAPH(,ga,)*,建立无向网络*,Graph*,ga,；,int,i，j，k；,float w；,for(i0；in；i+),ga,-,vexs,i,getchar,()；*,读入顶点信息，建立顶点表*,for(i0；in；i+),for(j0；jn；j+),ga,-arcsij0；*,邻接矩阵初始化*,for(k0；ke；k+)*,读入,e,条边*,(,scanf,(”ddf”，&I,&j，&w)；*,读入边(,v,i,，,v,j,),上的权,w*,ga,-arcsijw；,ga,-arcsjiw；,*CREATGRAPH*,该算法的执行时间,是,O(n+n,2,+e),，,其中,O(n,2,),的时问耗费在邻接矩阵的初始化操作上。因为,e,n,2,，,所以，算法的时间复杂度是,O(n,2,),。,邻接表,这种表示法类似于树的孩子链表表示法。,对于图,G,中的每个顶点,v,i,，,该方法把所有邻接于,v,i,的顶点,v,j,链成一个单链表，这个单链表就称为顶点,v,i,的邻接表(,Adjacency List)。,邻接表中每个表结点均有两个域，其一是邻接点域(,Adjvex,)，,用以存放与,v,i,相邻接的顶点,v,j,的序号；其二是链域(,Next)，,用来将邻接表的所有表结点链在一起。并且为每个顶点,v,i,的邻接表设置一个具有两个域的表头结点：一个是顶点域(,vertex)，,用来存放顶点,v,i,的信息；另一个是指针域(,Link)，,用于存入指向,v,i,的邻接表中第一个表结点的头指针。为了便于随机访问任一顶点的邻接表，将所有邻接表的表头结点顺序存储在一个向量中，这样，图,G,就可以由这个表头向量来表示。,建立有向图的邻接表与此类似，只是更加简单，每读入一个顶点对序号,i,，,j,时，仅需生成十个邻接点序号为,j,的边表结点，将其插入到,v,i,的出边表头部即可。若建立网络的邻接表，则需在边表的每个结点中增加一个存储边上权的数据域。,值得注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。,邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从空间及执行某些常用操作的时间这两方面来作一比较。,在邻接表(或逆邻接表)表示中，每个边表对应于邻接矩阵的一行(或一列)，边表中结点个数等于一行(或一列)中非零元素的个数。对于一个具有,n,个顶点,e,条边的图,G，,若,G,是无向图，则它的邻接表表示中有,n,个顶点表结点和2,e,个边表结点；若,G,是有向图，则它的邻接表表示或逆邻接表表示中均有,n,个顶点表结点和,e,个边表结点。因此邻接表或逆邻接表表示的空间复杂度为,S(n，e)O(n+e)。,若图中边的数目远远小于,n,2,(,即,en,2,)，,此类图称作稀疏图(,Sparse Graph)，,这时用邻接表表示比用邻接矩阵表示节省存储空间；若,e,接近于,n,2,(,准确地说，无向,图,e,接近于,n(n-1)2，,有向图,e,接近于,n(n-1)，,此类图称作稠密图(,Dense Graph)，,考虑到邻接表中要附加链域，则应取邻接矩阵表示法为宜。,在无向图中求顶点的度，邻接矩阵及邻接表两种存储结构都很容易做到：邻接矩阵中第,i,行,(,或第,i,列,),上非零元素的个数即为顶点,v,i,的度；在邻接表表示中，顶点,v,i,的度则是第,i,个边表中的结点个数。在有向图中求顶点的度。采用邻接矩阵表示比邻接表表示更方便：邻接矩阵中的第,i,行上非零元素的个数是顶点,v,i,的出度,OD(v,i,),，,第,i,列上非零元素的个数是顶点,v,i,的入度,ID(v,i,),，,顶点,v,i,的度即是二者之和；在邻接表表示中，第,i,个边表,(,即出边表,),上的结点个数是顶点,v,i,的出度，求,v,i,的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，而求顶点出度较难。,在邻接矩阵表示中，很容易判定,(,v,i,，,v,j,),或,v,i,，,v,j,是否是图的一条边，只要判定矩阵中的第,i,行第,j,列上的那个元素是否为零即可；但是在邻接表表示中，需扫描第,i,个边表，最坏情况下要耗费,O(n),时间。,在邻接矩阵中求边的数目,e，,必须检测整个矩阵，所耗费的时间是0(,n,2,)，,与,e,的大小无关；而在邻接表表示中，只要对每个边表的结点个数计数即可求得,e，,所耗费的时间是0(,e+n)。,因此，当,en,2,时，采用邻接表表示更节省时间。,图的遍历,和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对