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

图

图（Graph）是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。基本定义和术语

若图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)。

在一个有向图中，若存在一个顶点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)。通常权是具有某种意义的数.它们可以表示两个顶点之间的距离，耗费等用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：#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就可以由这个表头向量来表示。在邻接表(或逆邻接表)表示中，每个边表对应于邻接矩阵的一行(或一列)，边表中结点个数等于一行(或一列)中非零元素的个数。对于一个具有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。在该存储结构上执行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的两个邻接点已搜索过，故DFS(7)亦结束返回，回溯到v4。类似地由v4回溯到v2。V2的邻接点vl和v4已搜索过，但v2的第3个邻接点v5还尚未搜索，故接下来由v2搜索到v5，但因为v5已访问过，所以DFS(1)也结束返回，回溯到vl。vl的第1个邻接点已搜索过，故继续从v1搜索到第2个邻接点v3，因为v3未曾访问过，故调用DFS(2)。类似地依次访问v3，v6，v7后，又由v7依次回溯到v6，v3，vl。此时，vl的所有邻接点都已搜索过，故DFS(0)执行完毕。宽度优先搜索法宽度优先搜索(Breadth-First-Search)遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问过，在G中任选一顶点2为初始出发点，则宽度优先搜索的基本思想是：首先访问出发点Vi，接着依次访问vi的所有邻接点wl，w2，…，wt，然后，再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点，依此类推，直至图中所有和初始出发点v有路径相通的顶点都已访问到为止。此时，从vi开始的搜索过程结束，若G是连通图则遍历完成。显然，上述搜索法的特点是尽可能先对横向进行搜索，故称之为宽度优先搜索。设x和y是两个相继被访问过的顶点，若当前是以x为出发点进行搜索，则在访问x的所有未曾访问过的邻接点之后，紧接着是以y为出发点进行横向搜索，并对搜索到的y的邻接点中尚未被访问的顶点进行访问。也就是说，先访问的顶点其邻接点亦先被访问。为此，需引进队列保存已访问过的顶点。最小生成树

图的生成树不是唯一的，从不同的顶点出发进行遍历，可以得到不同的生成树。对于连通网络G＝(V，E)，边是带权的，因而G的生成树的各边也是带权的。我们把生成树各边的权值总和称为生成树的权，并把权最小的生成树称为G的最小生成树(MinimunSpanningTree)。生成树和最小生成树有许多重要的应用。令图G的顶点表示城市，边表示连接两个城市之间的通讯线路。n个城市之间最多可设立的线路有n(n-1)／2条，把n个城市连接起来至少要有n-1条线路，则图G的生成树表示了建立通讯网络的可行方案。如果给图中的边都赋予权，而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如何选择n-1条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢?这就是要构造该图的一棵最小生成树。

假设G＝(V，E)是连通网络，为简单起见，我们用序号1至n来表示顶点集合，即v＝{1，2，…，n}。设所求的最小生成树为T＝(U，TE)，其中U是T的顶点集，TE是T的边集。并且将G中边上的权看做是长度。Prim算法的基本思想是：首先从v中任取一个顶点u0，将生成树T置为仅有一个结点u0的树，即置U＝{u0}；然后只要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的最短边。最短路径交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短?交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路（从其他顶点达到)）。路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。所有顶点对之间的最短路径所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E)，要对G中任意一对顶点有序对V、W(V≠W)，找出V到W的最短距离和W到V的最短距离。解决此问题的一个有效方