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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,图,图（Graph）是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。,1,基本定义和术语,若图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,只有顶点而没有边，称为空图。,2,若,(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的,人度,(1ndegree)，记为ID(v)；把以顶点v为始点的边的数目，称为v的,出度,(outdegree)，记为OD(v)；顶点v的度则定义为该顶点的入度和出度之和，即D(v)ID(v)十OD(v)。,3,在无向图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的有向简单环。,4,在一个有向图中，若存在一个顶点,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,没有路径，但它有两个强连通分量，,5,若将图的每条边都赋上一个权，则称这种带权图为,网络,(Network)。通常权是具有某种意义的数.,6,它们可以表示两个顶点之间的距离，耗费等,7,图的存储结构,邻接矩阵,(Adjacency Matrix),是表示顶点之间相邻关系的矩阵。设,G,(V,，,E),是具有,n,个顶点的图，则,G,的邻接矩阵是具有如下性质的,n,阶方阵：,8,用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：,# define n 6 / * 图的顶点数 * /,# define e 8 / * 图的边（弧）数 */,typedef char vextype； / * 顶点的数据类型 * /,typedef float adjtype； / * 权值类型 * /,typedef struct,vextype vexsn；,adjtype arcsnn；,graph；,9,若图中顶点信息是,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 -vexsigetchar()；* 读入顶点信息，建立顶点表 *,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,),。,10,邻接表,这种表示法类似于树的孩子链表表示法。,对于图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就可以由这个表头向量来表示。,11,建立有向图的邻接表与此类似，只是更加简单，每读入一个顶点对序号,i,，,j,时，仅需生成十个邻接点序号为,j,的边表结点，将其插入到,v,i,的出边表头部即可。若建立网络的邻接表，则需在边表的每个结点中增加一个存储边上权的数据域。,值得注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。,邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从空间及执行某些常用操作的时间这两方面来作一比较。,12,在邻接表(或逆邻接表)表示中，每个边表对应于邻接矩阵的一行(或一列)，边表中结点个数等于一行(或一列)中非零元素的个数。对于一个具有n个顶点e条边的图G，若G是无向图，则它的邻接表表示中有n个顶点表结点和2e个边表结点；若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)，考虑到邻接表中要附加链域，则应取邻接矩阵表示法为宜。,13,在无向图中求顶点的度，邻接矩阵及邻接表两种存储结构都很容易做到：邻接矩阵中第,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,时，采用邻接表表示更节省时间。,14,图的遍历,和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图的所有顶点。然而，图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量visitedn，它的初值为false，一旦访问了顶点v,i,，便将visitedi-1置为TRUE。,15,深度优先搜索(Depth-First-Search)遍历类似于树的前序遍历。假设给定图G的初态是所有顶点均未访问过，在G中任选一顶点v,i,为初始出发点，则深度优先搜索可定义如下：首先，访问出发点v,i,，并将其标记为已访问过，然后，依次从v,i,出发搜索v,i,的每一个邻接点v,j,若v,j,未曾访问过，则以v,j,为新的出发点继续进行深度优先搜索。显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。例如，设x是刚访问过的顶点，按深度优先搜索方法，下一步将选择一条从x出发的未检测过的边(x，y)。若发现顶点y已被访问过，则重新选择另一条从x出发的未检测过的边。若发现顶点y未曾访问过，则沿此边从x到达y，访问y并将其标记为已访问过，然后从y开始搜索，直到搜索完从y出发的所有路径，才回溯到顶点x，然后再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是初始出发点，则回溯到在x之前被访问过的顶点；若x是初始出发点，则整个搜索过程结束。显然这时图G中所有和初始出发点有路径相通的顶点都已被访问过。因此，若G是连通图，则从初始出发点开始的搜索过程结束，也就意味着完成了对图G的遍历。,16,在该存储结构上执行DFS算法的过程如下：设初始出发点是v,1,，则DFS（0）的执行结果是访问v,1,，将其置上已访问标记，从v,1,搜索到的第1个邻接点是v,2,，因v,2,未曾访问过，故调用DFS(1)。执行DFS(1)，首先访问v,2,，将其标记为已访问过，然后从v,2,搜索到的第1个邻接点是v,l,，但v,l,已访问过，故继续搜索到第2个邻接点v,4,，v,4,未曾访过，因此调用DFS(3)。类似地分析，访问v,4,后调用DFS(7)，访问v：后调用DPS(4)。执行DFS(4)时，在访问v,5,并作标记后，从v,5,搜索到的两个邻接点依次是v,2,和v,8,，因为它们均已被访问过，所以DFS(4)执行结束返回，回溯到v,8,。又因为v,8,的两个邻接点已搜索过，故DFS(7)亦结束返回，回溯到v,4,。类似地由v,4,回溯到v,2,。V,2,的邻接点v,l,和v,4,已搜索过，但v,2,的第3个邻接点v,5,还尚未搜索，故接下来由v,2,搜索到v,5,，但因为v,5,已访问过，所以DFS(1)也结束返回，回溯到v,l,。v,l,的第1个邻接点已搜索过，故继续从v,1,搜索到第2个邻接点v,3,，因为v,3,未曾访问过，故调用DFS(2)。类似地依次访问v,3,，v,6,，v,7,后，又由v,7,依次回溯到v,6,，v,3,，v,l,。此时，v,l,的所有邻接点都已搜索过，故DFS(0)执行完毕。,17,宽度优先搜索法,宽度优先搜索,(Breadth-First-Search),遍历类似于树的按层次遍历。设图,G,的初态是所有顶点均未访问过，在,G,中任选一顶点,2,为初始出发点，则宽度优先搜索的基本思想是：首先访问出发点,V,i,，接着依次访问,v,i,的所有邻接点,w,l,，,w,2,，,w,t,，然后，再依次访问与,w,l,，,w,2,，,w,t,邻接的所有未曾访问过的顶点，依此类推，直至图中所有和初始出发点,v,有路径相通的顶点都已访问到为止。此时，从,v,i,开始的搜索过程结束，若,G,是连通图则遍历完成。,显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为宽度优先搜索。设x和y是两个相继被访问过的顶点，若当前是以x为出发点进行搜索，则在访问x的所有未曾访问过的邻接点之后，紧接着是以y为出发点进行横向搜索，并对搜索到的y的邻接点中尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点亦先被访问。为此，需引进队列保存已访问过的顶点。,18,最小生成树,图的生成树不是唯一的，从不同的顶点出发进行遍历，可以得到不同的生成树。对于连通网络,G,(V,，,E),，边是带权的，因而,G,的生成树的各边也是带权的。我们把生成树各边的权值总和称为生成树的权，并把权最小的生成树称为,G,的,最小生成树,(Minimun Spanning Tree),。,生成树和最小生成树有许多重要的应用。令图G的顶点表示城市，边表示连接两个城市之间的通讯线路。n个城市之间最多可设立的线路有n(n-1)2条，把n个城市连接起来至少要有n-1条线路，则图G的生成树表示了建立通讯网络的可行方案。如果给图中的边都赋予权，而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如何选择n-1条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢?这就是要构造该图的一棵最小生成树。,19,以下我们只讨论无向图的最小生成树问题。构造最小生成树可以有多种算法，其中大多数构造算法都是利用了最小生成树的下述性质：设G(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(即uU)里、另一个端点不在U(即vV-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包含此边(u，v)。这个性质称为MST性质。MST性质可用反证法证明：假设G的任何一棵最小生成树中都不含边(u，v)。设T是G的一棵最小生成树，但不包含边(u，v)。由于T是树，且是连通的，因此有一条从u到v的路径；且该路径上必有一条连接两个顶点集U和V-U的边(u，v)，其中uU，vV-U，否则u和v不连通。当把边(u，v)加入树T时，得到一个含有边(u，v)的回路，见图7-15。删去边(u，v)，上述回路即被消除，由此得到另一棵生成树T，T和T的区别仅在于用边(u，v)取代了T中的边(u，v)。因为(u，v)的权(u，v)的权，故T的权T的权，因此T也是G的最小生成树，它包含边(u，v)，与假设矛盾!,20,假设,G,(V,，,E),是连通网络，为简单起见，我们用序号,1,至,n,来表示顶点集合，即,v,1,，,2,，,n,。设所求的最小生成树为,T,(U,，,TE),，其中,U,是,T,的顶点集，,TE,是,T,的边集。并且将,G,中边上的权看做是长度。,Prim,算法的基本思想是：首先从,v,中任取一个顶点,u,0,，将生成树,T,置为仅有一个结点,u,0,的树，即置,U,u,0,；然后只要,U,是,V,的真子集，就在所有那些其一个端点,u,己在,T(,即,u,U),、另一个端点,v,还未在,T(,即,v,V,U),的边中，找一条最短,(,即权最小,),的边,(u,，,v),，并把该条边,(u,，,v),和其不在,T,中的顶点,v,，分别并入,T,的边集,TE,和顶点集,U,。如此进行下去，每次往生成树里并入一个顶点和一条边，直到把所有顶点都包括进生成树,T,为止。此时，必有,U,V,，,TE,中有,n-1,条边。,MST,性质保证上述过程求得的,T,(U,，,TE),是,G,的一棵最小生成树。,显然，Prim算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。为直观解释方便，设想在构造过程中，T的顶点集U中顶点和边集TE中的边均被涂成红色，U之外的顶点集V-U中的顶点均被涂成蓝色，连接红点和蓝点的边均被涂成紫色，那么最短紫边就是连接U和V-U的最短边。,21,最短路径,交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短? 交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上,权,值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。,另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路（从其他顶点达到)）。路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。,22,所有顶点对之间的最短路径,所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E)，要对G中任意一对顶点有序对V、W(VW)，找出V到W的最短距离和W到V的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点，重复执行迪杰斯特拉算法n次，即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n,3,)。,23,弗洛伊德算法仍然使用前面定义的图的邻接矩阵costn+1n+1来存储带权有向图。算法的基本思想是:设置一个nxn的矩阵A,(k),，其中除对角线的元素都等于0外，其他元素a,(k),ij表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，当K=0时，A,(0),ij=arcsij,以后逐步尝试在原路径中加入其他顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：第一步，让所有边上加入中间顶点1，取Aij与Ai1+A1j中较小的值作Aij的值，完成后得到A,(1),，第二步，让所有边上加入中间顶点2，取Aij与Ai2+A2j中较小的值，完成后得到A,(2),，如此进行下去，当第n步完成后，得到A,(n),，A,(n),即为我们所求结果，A,(n),ij表示顶点i到顶点j的最短距离。,24,拓扑排序,通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，整个工程也就完成了。例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图7-24给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须学完高等数学。在图7-24（b）中，我们用一种有向图来表示课程开设，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络(Active On Vertices)简称为AOV网。,25,在AOV网中，有向边表示i活动应先于j活动开始，即i活动必须完成后，j活动才可以开始，并称i为j的直接前驱，j为i的直接后继。这种前驱与后继的关系有传递性，此外，任何活动i不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看，AOV网中不能出现有向回路（或称有向环）。在AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。对程序流程而言，将出现死循环。因此，对给定的AOV网，应先判断它是否存在有向环。判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。,26,本章小结,图是一种复杂的非线性结构，具有广泛的应用背景。本章涉及到的基本概念有：,图,：由两个集合V和E组成，记为G(V，E)，其中v是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶点而没有边，称为空图。,有向图（Digraph）,：若图G中的每条边都是有方向的，则称G为有向图。,无向图（Undigraph）：,若图G中的每条边都是没有方向的，则称G为无向图。,无向完全图(Undirected Complete Graph)：,恰好有n(n-1)2条边的无向图称为无向完全图。,有向完全图(Directed Complete Graph),：恰有n(n-1)条边的有向图称为有向完全图。,邻接点(Adjacent),：若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点。,度(Degree),：无向图中顶点v的度是关联于该顶点的边的数目。,人度(1ndegree),若G为有向图，则把以顶点v为终点的边的数目，称为v的人度，记为ID(v)。,出度(outdegree),：把以顶点v为始点的边的数目，称为v的出度，记为OD(v)。,子图(Subgraph),：设G(V，E)是一个图，若v,是v的子集，E,是E的子集，且E,中的边所关联的顶点均在v,中，则G,(V,，E,)也是一个图，并称其为G的子图。,27,路径(Path),：在无向图G中，若存在一个顶点序列vp,vi1,vi2，vin，vq，使得(vp，vil)，(vi1,vi2)，(vin，vq)均属于E(G)，则称顶点vp到vq存在一条路径。,路径长度,：该路径上边的数目。,简单路径,：若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。,简单回路或简单环(Cycle),：起点和终点相同(vpvq)的简单路径称为简单回路或简单环。,有根图,：在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。,连通,：在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。,连通图(Connected Graph),：若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图。,连通分量(connected Component),：无向图G的极大连通子图称为G的连通分量。,强连通图,：在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。,强连通分量,：有向图G的极大强连通子图称为G的强连通分量。,网络(Network),：若将图的每条边都赋上一个权，则称这种带权图为网络。,生成树(Spanning Tree),：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。,最小生成树(Minimun Spanning Tree),：权最小的生成树称为G的最小生成树。,本章在介绍图的基本概念的基础上，还介绍了图的两种常用的存储结构，对图的遍历、最小生成树等问题做了较详细的讨论，给出了相应的求解算法，有的算法采用自顶向下、逐步求精的方法加以介绍，也许能便于读者理解它们。,相对而言之，图这一章内容较难，尤其是离散数学基础较差的读者，也许难度更大些。建议读者知难而进，理解本章所介绍的算法实质，掌握图的有关术语和存储表示。面对实际问题时，学会引用本章的有关内容。,28,