数据结构 图的介绍

基本定义和术语•若图G中的每条边都是有方向的，则称G为有向图（Digraph）。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，＜vi，vj＞表示一条有向边，vi是边的始点（起点），vj是边的终点。因此，＜vi，vj＞和＜vj，vi＞是两条不同的有向边。有向边也称为弧（Arc），边的始点称为弧尾（Tail），终点称为弧头（Head）。•图G由两个集合V和E组成，记为G＝(V，E)，其中v是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶点而没有边，称为空图。若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点(Adjacent)，或称vi和vj相邻接；称(vi，vj)关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联。如图7-1中G2，与顶点vl相邻接的顶点是v2，v3和v4，而关联于顶点v2的边是(vl，v2)，(v2，v3)和(v2，v4)。若＜vi，vj＞是一条有向边，则称顶点vi邻接到vj,顶点vj邻接于顶点vi,并称边＜vi，vj＞关联于vi和vj或称＜vi，vj＞与顶点vi和vj相关联。如图7-1中Gl，关联于顶点v2的边是＜v1，v2＞，＜v2，vl＞和＜v2,v3＞。无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。若G为有向图，则把以顶点v为终点的边的数目，称为v的人度(1ndegree)，记为ID(v)；把以顶点v为始点的边的数目，称为v的出度(outdegree)，记为OD(v)；顶点v的度则定义为该顶点的入度和出度之和，即D(v)＝ID(v)十OD(v)。在无向图G中，若存在一个顶点序列vp,vi1,vi2…，vin，vq，使得(vp，vil)，(vi1,vi2)，…，(vin，vq)均属于E(G)，则称顶点vp到vq存在一条路径(Path)。若G是有向图，则路径也是有向的，它由E(G)中的有向边＜vp，vil＞，＜vil，vi2＞，…，＜vin，vq＞组成。路径长度定义为该路径上边的数目。若一条路径上除了vp和vq可以相同外；其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同(vp＝vq)的简单路径称为简单回路或简单环(Cycle)。例如，在图G2中顶点序列vl,v2，v3，v4是一条从顶点vl到顶点v4的长度为3的简单路径；顶点序列vl,v2，v4，vl，v3是一条从顶点vl到顶点v3的长度为4的路径，但不是简单路径；顶点序列vl，v2，v4，vl是一个长度为3的简单环。在有向图Gl中，顶点序列vl，v2，vl是一个长度为2的有向简单环。在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(ConnectedGraph)。例如，图G2和G3是连通图。无向图G的极大连通子图称为G的连通分量(connectedComponent)。显然，任何连通图的连通分量只有一个，即是其自身，而非连通的无向图有多个连通分量。例如，图7-4中的G4是非连通图，它有两个连通分量Hl和H2。在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。例如图7-1中的Gl不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。通常权是具有某种意义的数.它们可以表示两个顶点之间的距离，耗费等图的存储结构•邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。设G＝(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：）中的边（不是）或：若（）中的边（是）或：若（GEvvvvGEvvvvjijijiji,,0,,1ji,A•用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：•#definen6/*图的顶点数*/•#definee8/*图的边（弧）数*/•typedefcharvextype；/*顶点的数据类型*/•typedeffloatadjtype；/*权值类型*/•typedefstruct•{vextypevexs[n]；•adjtypearcs[n][n]；•}graph；•若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对称的，故可采用压缩存储的方法，仅存储下三角阵(不包括对角线上的元素)中的元素即可。显然，邻接矩阵表示法的空间复杂度S(n)＝O(n2)。•CREATGRAPH(ga)／*建立无向网络*／•Graph*ga；•{•inti，j，k；•floatw；•for(i＝0；i＜n；i++)•ga-vexs[i]＝getchar()；／*读入顶点信息，建立顶点表*／•for(i＝0；i＜n；i++)•for(j＝0；j＜n；j++)•ga-arcs[i][j]＝0；／*邻接矩阵初始化*／•for(k＝0；k＜e；k++)／*读入e条边*／•(scanf(”％d％d％f”，&I,&j，&w)；／*读入边(vi，vj)上的权w*／•ga-arcs[i][j]＝w；•ga-arcs[j][i]＝w；•}•}／*CREATGRAPH*／•该算法的执行时间是O(n+n2+e)，其中O(n2)的时问耗费在邻接矩阵的初始化操作上。因为e＜n2，所以，算法的时间复杂度是O(n2)。邻接表这种表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表(AdjacencyList)。邻接表中每个表结点均有两个域，其一是邻接点域(Adjvex)，用以存放与vi相邻接的顶点vj的序号；其二是链域(Next)，用来将邻接表的所有表结点链在一起。并且为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个是顶点域(vertex)，用来存放顶点vi的信息；另一个是指针域(Link)，用于存入指向vi的邻接表中第一个表结点的头指针。为了便于随机访问任一顶点的邻接表，将所有邻接表的表头结点顺序存储在一个向量中，这样，图G就可以由这个表头向量来表示。建立有向图的邻接表与此类似，只是更加简单，每读入一个顶点对序号＜i，j＞时，仅需生成十个邻接点序号为j的边表结点，将其插入到vi的出边表头部即可。若建立网络的邻接表，则需在边表的每个结点中增加一个存储边上权的数据域。值得注意的是，一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从空间及执行某些常用操作的时间这两方面来作一比较。在邻接表(或逆邻接表)表示中，每个边表对应于邻接矩阵的一行(或一列)，边表中结点个数等于一行(或一列)中非零元素的个数。对于一个具有n个顶点e条边的图G，若G是无向图，则它的邻接表表示中有n个顶点表结点和2e个边表结点；若G是有向图，则它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此邻接表或逆邻接表表示的空间复杂度为S(n，e)＝O(n+e)。若图中边的数目远远小于n2(即e＜＜n2)，此类图称作稀疏图(SparseGraph)，这时用邻接表表示比用邻接矩阵表示节省存储空间；若e接近于n2(准确地说，无向图e接近于n(n-1)／2，有向图e接近于n(n-1))，此类图称作稠密图(DenseGraph)，考虑到邻接表中要附加链域，则应取邻接矩阵表示法为宜。在无向图中求顶点的度，邻接矩阵及邻接表两种存储结构都很容易做到：邻接矩阵中第i行(或第i列)上非零元素的个数即为顶点vi的度；在邻接表表示中，顶点vi的度则是第i个边表中的结点个数。在有向图中求顶点的度。采用邻接矩阵表示比邻接表表示更方便：邻接矩阵中的第i行上非零元素的个数是顶点vi的出度OD(vi)，第i列上非零元素的个数是顶点vi的入度ID(vi)，顶点vi的度即是二者之和；在邻接表表示中，第i个边表(即出边表)上的结点个数是顶点vi的出度，求vi的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，而求顶点出度较难。在邻接矩阵表示中，很容易判定(vi，vj)或＜vi，vj＞是否是图的一条边，只要判定矩阵中的第i行第j列上的那个元素是否为零即可；但是在邻接表表示中，需扫描第i个边表，最坏情况下要耗费O(n)时间。在邻接矩阵中求边的数目e，必须检测整个矩阵，所耗费的时间是0(n2)，与e的大小无关；而在邻接表表示中，只要对每个边表的结点个数计数即可求得e，所耗费的时间是0(e+n)。因此，当e＜＜n2时，采用邻接表表示更节省时间。图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图的所有顶点。然而，图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量visited[n]，它的初值为false，一旦访问了顶点vi，便将visited[i-1]置为TRUE。深度优先搜索(Depth-First-Search)遍历类似于树的前序遍历。假设给定图G的初态是所有顶点均未访问过，在G中任选一顶点vi为初始出发点，则深度优先搜索可定义如下：首先，访问出发点vi，并将其标记为已访问过，然后，依次从vi出发搜索vi的每一个邻接点vj,若vj未曾访问过，则以vj为新的出发点继续进行深度优先搜索。显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。例如，设x是刚访问过的顶点，按深度优先搜索方法，下一步将选择一条从x出发的未检测过的边(x，y)。若发现顶点y已被访问过，则重新选择另一条从x出发的未检测过的边。若发现顶点y未曾访问过，则沿此边从x到达y，访问y并将其标记为已访问过，然后从y开始搜索，直到搜索完从y出发的所有路径，才回溯到顶点x，然后再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是初始出发点，则回溯到在x之前被访问过的顶点；若x是初始出发点，则整个搜索过程结束。显然这时图G中所有和初始出发点有路径相通的顶点都已被访问过。因此，若G是连通图，则从初始出发点开始的搜索过程结束，也就意味着完成了对图G的遍历。在该存储结构上执行DFS算法的过程如下：设初始出发点是v1，则DFS（0）的执行结果是访问v1，将其置上已访问标记，从v1搜索到的第1个邻接点是v2，因v2未曾访问过，故调用DFS(1)。执行DFS(1)，首先访问v2，将其标记为已访问过，然后从v2搜索到的第1个邻接点是vl，但vl已访问过，故继续搜索到第2个邻接点v4，v4未曾访过，因此调用DFS(3)。类似地分析，访问v4后调用DFS(7)，访问v：后调用DPS(4)。执行DFS(4)时，在访问v5并作标记后，从v5搜索到的两个邻接点依次是v2和v8，因为它们均已被访问过，所以DFS(4)执行结束返回，回溯到v8。又因为v8的