1、NoImage第第7章章 图图7.1 图的定义与基本术语图的定义与基本术语 7.2 图的存储结构图的存储结构 7.3 图的遍历图的遍历 7.4 图的连通性问题图的连通性问题 7.5 有向无环图的应用有向无环图的应用 7.6 最短路径最短路径返回主目录NoImage 图结构与表结构和树结构的不同表现在结点之图结构与表结构和树结构的不同表现在结点之间的关系上，线性表中结点之间的关系是一对一的；间的关系上，线性表中结点之间的关系是一对一的；树是按分层关系组织的结构，树结构之间是一对多；树是按分层关系组织的结构，树结构之间是一对多；对于图结构，图中顶点之间的关系可以是多对多，对于图结构，图中顶点之间的
2、关系可以是多对多，即一顶点和其它顶点间的关系是任意的，可以有关即一顶点和其它顶点间的关系是任意的，可以有关也可以无关。因此，图也可以无关。因此，图 G 树树T L，图是一种比，图是一种比较复杂的非线性数据结构。较复杂的非线性数据结构。图作为一种非线性结构，被广泛应用于多个技术图作为一种非线性结构，被广泛应用于多个技术领域。在本章中，主要是应用图论的理论知识来讨论领域。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。决一些实际问题。返回主目录NoImage7.1 图的定义与基本术语图的定义与基本术
3、语7.1.1 图的定义图的定义 图（图（Graph）是一种网状数据结构，其形式化）是一种网状数据结构，其形式化定义如下：定义如下：Graph=（V，R）V=xxDataObjectxDataObject R=VR VR=xPyP（x x，y y）（x x，yVyV）返回主目录NoImage DataObject DataObject为一个集合，该集合中的为一个集合，该集合中的所有元素所有元素具有具有相同的特性相同的特性。V中的数据元素通常称为中的数据元素通常称为顶点顶点（vertex），），VR是两个顶点之间的关系的集合。是两个顶点之间的关系的集合。P P（x x，y y）表示）表示x x和和
4、y y之间有特定的关联属性之间有特定的关联属性P P。弧：弧：若若VR，则，则表示从顶点表示从顶点x到顶点到顶点y的的一条弧一条弧（arc），并称），并称x为为弧尾弧尾（tail）或）或起始点起始点，称称y为为弧头弧头（head）或）或终端点终端点。有向图：有向图：若图中的边是有方向的，称这样的图为若图中的边是有方向的，称这样的图为有有向图向图。返回主目录NoImage无向图无向图：若若VR，必有，必有VR，即，即VR是对称关系，这时以无序对（是对称关系，这时以无序对（x，y）来代替两）来代替两个有序对，表示个有序对，表示x和和y之间的一条边（之间的一条边（edge），此），此时的图称为时的图
5、称为无向图无向图。例如：下图例如：下图G1是有向图，是有向图，G2是无向图是无向图2134G12145G23返回主目录NoImage 在图中，我们可以将任一顶点看成是图的第一在图中，我们可以将任一顶点看成是图的第一个顶点，同理，对于任一顶点而言，它的邻接点之个顶点，同理，对于任一顶点而言，它的邻接点之间也不存在顺序关系。为了操作的方便，我们需要间也不存在顺序关系。为了操作的方便，我们需要将图中的顶点按任意序列排列起来。将图中的顶点按任意序列排列起来。顶点顶点在这个在这个人人为的随意排列中的位置序号称为为的随意排列中的位置序号称为顶点在图中的位置。顶点在图中的位置。图的基本操作和其它数据结构一样
6、，也有创图的基本操作和其它数据结构一样，也有创建、插入、删除、查找等。建、插入、删除、查找等。返回主目录NoImage图的抽象类型定义：图的抽象类型定义：ADT Graph 数据对象数据对象V：一个集合，该集合中的所有元素具有相：一个集合，该集合中的所有元素具有相同的特性。同的特性。数据关系数据关系R：R=VR VR=P（x，y）（x，yV）返回主目录NoImage基本操作基本操作：（1）GreateGraph(G)：创建图：创建图G。（2）DestoryGraph(G)：销毁图：销毁图G。（3）LocateVertex(G,v)：确定顶点确定顶点v v在图在图G G中的位置。中的位置。若图若
7、图G G中没有顶点中没有顶点v v，则函数值为，则函数值为“空空”。（4 4）GetVertex(G,I)GetVertex(G,I)：取出图：取出图G G中的第中的第i i个顶点的个顶点的值。值。若若ii图图G G中顶点数，则函数值为中顶点数，则函数值为“空空”。返回主目录NoImage（5）FirstAdjVertex(G,v)FirstAdjVertex(G,v)：求图：求图G G中顶点中顶点v v的第一的第一个邻接点。若个邻接点。若v v无邻接点或图无邻接点或图G G中无顶点中无顶点v v，则函数值，则函数值为为“空空”。（6）NextAdjVertex(G,v,w)NextAdjVe
8、rtex(G,v,w)：已知：已知w w是图是图G G中顶点中顶点v v的某个邻接点，求顶点的某个邻接点，求顶点v v的下一个邻接点（紧跟在的下一个邻接点（紧跟在w w后面）。若后面）。若w w是是v v的最后一个邻接点，则函数值为的最后一个邻接点，则函数值为“空空”。（7）InsertVertex(G,u)InsertVertex(G,u)：在图：在图G G中增加一个顶点中增加一个顶点u u。返回主目录NoImage（8）DeleteVertexDeleteVertex（G G，v v）：删除图）：删除图G G的顶点的顶点v v及及与与顶点顶点v v相关联的弧。相关联的弧。（9）Insert
9、ArcInsertArc（G G，v v，w w）：在图）：在图G G中增加一条从中增加一条从顶点顶点v v到顶点到顶点w w的弧。的弧。（10）DeleteArcDeleteArc（G G，v v，w w）：删除图）：删除图G G中从顶点中从顶点v v到顶点到顶点w w的弧。的弧。（11）TraverseGraphTraverseGraph（G）：按照某种次序，对图）：按照某种次序，对图G的每个结点访问一次且最多一次。的每个结点访问一次且最多一次。返回主目录NoImage7.1.2 基本术语基本术语 设用设用n表示图中顶点的个数，用表示图中顶点的个数，用 e表示图中边或表示图中边或弧的数目，
10、并且不考虑图中每个顶点到其自身的边弧的数目，并且不考虑图中每个顶点到其自身的边或弧。或弧。无向完全图无向完全图：有有n（n-1）/2条边（图中每个顶点和条边（图中每个顶点和其余其余n-1个顶点个顶点都有边相连都有边相连）的无向图为无向完全）的无向图为无向完全图图。有向完全图有向完全图：有有n（n-1）条边（图中每个顶点和其）条边（图中每个顶点和其余余n-1个顶点个顶点都有弧相连都有弧相连）的有向图为有向完全图）的有向图为有向完全图。返回主目录NoImage稀疏图稀疏图：对于有很少条边的图（对于有很少条边的图（e n log n）称为）称为稀疏图稀疏图，反之称为反之称为稠密图稠密图。子图子图：设
11、有两个图设有两个图G=（V，E）和图）和图G/=（V/，E/）,若若V/V且且E/E，则称图则称图G/为为G的子图。的子图。图图G1和图和图G2的子图见的子图见p155的图的图7.2所示。所示。返回主目录NoImage 对于对于无向图无向图 G=（V，E），如果边（），如果边（v，v/）E，则称顶点，则称顶点v，v/互为邻接点，即互为邻接点，即v，v/相邻接。相邻接。边（边（v，v/）依附于顶点）依附于顶点v和和v/，或者说边（，或者说边（v，v/）与顶点与顶点v和和v/相关联。相关联。对于对于有向图有向图G=（V，A）而言，若弧）而言，若弧A，则称顶点，则称顶点v邻接到顶点邻接到顶点v/，顶
12、点，顶点v/邻接自顶邻接自顶点点v，或者说弧，或者说弧与顶点与顶点v，v/相关联。相关联。邻接点邻接点：返回主目录NoImage度、入度和出度度、入度和出度 对于对于无向图而言，无向图而言，顶点顶点v 的度的度是是指和指和v相关联的边的相关联的边的数目数目，记作，记作TD（v）。对于有向图而言，对于有向图而言，顶点顶点v的度有的度有出度出度和和入度入度两部分：两部分：以以顶点顶点v为弧头的弧的数目为弧头的弧的数目称为该顶点的称为该顶点的入度入度，记，记作作ID（v），以，以顶点顶点v为弧尾的弧的数目为弧尾的弧的数目称为该顶点称为该顶点的的出度出度，记作，记作OD（v）则顶点则顶点v的度为：的度
13、为：TD（v）=ID（v）+OD（v）。）。返回主目录NoImage 一般地，若图一般地，若图G中有中有n个顶点，个顶点，e条边或弧，则条边或弧，则图中顶点的度与边的关系如下：图中顶点的度与边的关系如下：e=TD(Vi)2ni=1返回主目录NoImage权与网权与网:在实际应用中，有时图的在实际应用中，有时图的边或弧上边或弧上往往与具有往往与具有一定意义的数有关一定意义的数有关，即，即每一条边都有与它相关的数，每一条边都有与它相关的数，称为称为权权，这些权可以表示从一个顶点到另一个顶点，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将的距离或耗费等信息。我们将这种带权的图这种带权
14、的图叫做叫做赋赋权图或网权图或网。图例见图例见p156的图的图7.3所示。所示。返回主目录NoImage路径与回路路径与回路无向图无向图G=G=（V V，EE）中从）中从顶点顶点v v到到v v/的的路径路径是一个顶是一个顶点序列点序列v vi 0i 0，v vi1i1，v vi2i2，v vinin，其中（，其中（v vij-1ij-1，v vijij）EE，1jn1jn。如果图如果图G G是是有向图有向图，则，则路径路径也是也是有向有向的，顶点序列应的，顶点序列应满足满足vAA，1jn1jn。路径长度路径长度：指路径上经过的弧或边的数目。：指路径上经过的弧或边的数目。返回主目录NoImag
15、e回路或环回路或环：在一个路径中，若其第一个顶点和最后：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即一个顶点是相同的，即v=vv=v/，则称该路径为一个，则称该路径为一个回路或环回路或环。简单路径：简单路径：若表示路径的顶点序列中的顶点若表示路径的顶点序列中的顶点各不相各不相同同，则称这样的路径为，则称这样的路径为简单路径简单路径。简单回路：简单回路：除了除了第一个和最后一个顶点外，其余各第一个和最后一个顶点外，其余各顶点顶点均不重复出现均不重复出现的回路为的回路为简单回路简单回路。返回主目录NoImage连通图连通图 连通图：连通图：在无向图在无向图G=G=（V V，EE）中，若从
16、）中，若从v vi i到到v vj j有路有路径相通，则称顶点径相通，则称顶点v vi i与与v vj j是连通的。如果对于图中的是连通的。如果对于图中的任意两个顶点任意两个顶点v vi i、v vj jVV，v vi i，v vj j都是连通的，则称都是连通的，则称该无向图该无向图G G为连通图。为连通图。连通分量连通分量：无向图中的：无向图中的极大连通子图极大连通子图称为该无向图称为该无向图的连通分量。的连通分量。返回主目录NoImage强连通图强连通图：在有向图：在有向图G=G=（V V，AA）中，若对于每对）中，若对于每对顶点顶点v vi i、v vj jVV且且v vi ivvj j
17、，从，从vivi到到v vj j和和v vj j到到v vi i都有路都有路径，则称该有向图为强连通图。径，则称该有向图为强连通图。强连通分量：强连通分量：有向图的有向图的极大强连通子图极大强连通子图称作有向图称作有向图的强连通分量的强连通分量。图图G1和图和图G3的连通分量见的连通分量见p157的图的图7.4所示所示返回主目录NoImage生成树生成树一个连通图的生成树是指一个一个连通图的生成树是指一个极小连通子图极小连通子图，它含，它含有图中的有图中的全部顶点全部顶点，但只有足已构成一棵树的，但只有足已构成一棵树的n-1n-1条边。条边。如图如图p157的图的图7.5所示。所示。返回主目录
18、NoImage7.2 图的存储结构图的存储结构图的存储结构方法有：图的存储结构方法有：邻接矩阵表示法；邻接矩阵表示法；邻接表；邻接表；邻接多重表；邻接多重表；十字链表十字链表 返回主目录NoImage邻接矩阵表示法邻接矩阵表示法 图的邻接矩阵表示法图的邻接矩阵表示法（Adjacency Matrix）也称作也称作数组表示法数组表示法。它采用它采用两个数组两个数组来表示图：一个是用于来表示图：一个是用于存储顶点信存储顶点信息息的一维数组，另一个是用于的一维数组，另一个是用于存储图中顶点之间关存储图中顶点之间关联关系联关系的二维数组，这个的二维数组，这个关联关系数组关联关系数组被称为被称为邻接邻接
19、矩阵矩阵。返回主目录NoImage若若G是一具有是一具有n个顶点的无权图，个顶点的无权图，G的邻接矩阵是具的邻接矩阵是具有如下性质的有如下性质的nn矩阵矩阵A：Ai,j=若若或（或（vi,vj)VR 0 反之反之G1和和G2的邻接矩阵见的邻接矩阵见p158的图的图7.6所示所示返回主目录NoImage若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具个顶点的网，则它的邻接矩阵是具有如下性质的有如下性质的nn矩阵矩阵A：Ai,j=Wij 若若或（或（vi,vj)VR 反之反之有向网及其邻接矩阵见有向网及其邻接矩阵见p158的图的图7.7所示。所示。返回主目录NoImage邻接矩阵表示法的
20、邻接矩阵表示法的C语言类型描述为：语言类型描述为：#define MAX_VERTEX_NUM 10 /*最多顶点个数*/#define INFINITY 32768 /*最多顶点个数*/typedef enumDG,DN,UDG,UDN GraphKind;/*图的种类：DG表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向网*/typedef char VertexData;/*假设顶点数据为字符型*/typedef struct ArcNode AdjType adj;/*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/OtherInfo info;ArcNode;
21、返回主目录NoImagetypedef struct VertexData vexsMAX_VERTEX_NUM;/*顶点向量*/ArcNode arcs MAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接矩阵*/int vexnum,arcnum;/*图的顶点数和弧数*/GraphKind kind;/*图的种类标志*/AdjMatrix;/*（Adjacency Matrix Graph）*/返回主目录NoImage邻接矩阵法的特点：邻接矩阵法的特点：1.存储空间：对于无向图而言，它的邻接矩阵是对存储空间：对于无向图而言，它的邻接矩阵是对称矩阵，所以可采用压缩存储法（下三角
22、），其存称矩阵，所以可采用压缩存储法（下三角），其存储空间只需储空间只需n(n-1)/2。但对于有向图而言，因为它。但对于有向图而言，因为它的弧是有方向的，它的邻接矩阵不一定是对称矩阵，的弧是有方向的，它的邻接矩阵不一定是对称矩阵，所以需要所以需要n2个存储空间。个存储空间。2.便于运算：便于运算：采用邻接矩阵表示法，便于判定图采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据中任意两个顶点之间是否有边相连，即根据Ai，j=0或或1来判断。另外还便于求得各个顶点的度。来判断。另外还便于求得各个顶点的度。返回主目录NoImage 对于对于无向图无向图而言，其邻接矩阵第而言，其邻
23、接矩阵第 i 行元素之和就行元素之和就是图中第是图中第 i 个顶点的度：个顶点的度：TD(vi)=Ai,j j=1n 对于对于有向图有向图而言，其邻接矩阵第而言，其邻接矩阵第i行元素之和就是行元素之和就是图中第图中第i个顶点的出度，个顶点的出度，第第i i列元素之和就是图中第列元素之和就是图中第i i个顶点的入度。个顶点的入度。OD(vi)=Ai,j j=1nID(vi)=Aj,i j=1n顶点顶点i的出度：的出度：顶点顶点i的入度：的入度：返回主目录NoImage采用邻接矩阵存储法表示图，很便于实现图的一些采用邻接矩阵存储法表示图，很便于实现图的一些基本操作，如基本操作，如 FirstAdj
24、VertexFirstAdjVertex（G G，v v）：）：（1）首先，由首先，由LocateVertexLocateVertex（G G，v v）找到）找到v v在图中在图中的位置，即的位置，即v v在一维数组在一维数组vexsvexs中的序号中的序号i i。（2）二维数组二维数组arcsarcs中第中第i i行上第一个行上第一个adjadj域非零的域非零的分量所在的列号分量所在的列号j j，便是，便是v v的第一个邻接点在图的第一个邻接点在图G G中的中的位置。位置。（3）取出一维数组取出一维数组vexsjvexsj中的数据信息，即与顶中的数据信息，即与顶点点v v邻接的第一个邻接点的
25、信息。邻接的第一个邻接点的信息。注意注意：稀疏图不适于用邻接矩阵来存储，因为这样：稀疏图不适于用邻接矩阵来存储，因为这样会造成存储空间的浪费。会造成存储空间的浪费。返回主目录NoImage用邻接矩阵法创建有向网的算法如下：用邻接矩阵法创建有向网的算法如下：int LocateVertex(AdjMatrix*G,VertexData v)/*求顶点位置函数求顶点位置函数*/int j=Error,k;for(k=0;kvexnum;k+)if(G-vexsk=v)j=k;break;return(j);返回主目录NoImageint CreateDN(AdjMatrix*G)/*创建一个有向网
26、创建一个有向网*/int i,j,k,weight;VertexData v1,v2;scanf(%d,%d,&G-arcnum,&G-vexnum);/*输入图的顶点数和弧数输入图的顶点数和弧数*/for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;for(i=0;ivexnum;i+)scanf(%c,&G-vexsi);/*输入图的顶点输入图的顶点*/for(k=0;karcnum;k+)返回主目录NoImage scanf(%c,%c,%d,&v1,&v2,&weight);/*输入一条弧的两个顶点及权值输入一条弧的两
27、个顶点及权值*/i=LocateVex_M(G,v1);j=LocateVex_M(G,v2);G-arcsij.adj=weight;/*建立弧建立弧*/return(Ok);分析分析：该算法的时间复杂度为：该算法的时间复杂度为O O（n n2 2+e+en n），其中），其中 O O（n n2 2）时间耗费在对二维数组）时间耗费在对二维数组arcsarcs的每个分量的的每个分量的arjarj域初始化赋值上。域初始化赋值上。O O（e en n）的时间耗费在有向）的时间耗费在有向网中边权的赋值上。网中边权的赋值上。返回主目录NoImage邻接表表示法邻接表表示法邻接表（邻接表（Adjacen
28、cy List）表示法实际上是图的一种）表示法实际上是图的一种链式存储结构。链式存储结构。它的基本思想是只存有关联的信息，它的基本思想是只存有关联的信息，对于图中存在的边信息则存储，而对于不相邻接的对于图中存在的边信息则存储，而对于不相邻接的顶点则不保留信息顶点则不保留信息。在邻接表中，对图中的每个顶。在邻接表中，对图中的每个顶点建立一个带头结点的边链表，每个边链表的头结点建立一个带头结点的边链表，每个边链表的头结点又构成一个表头结点表。点又构成一个表头结点表。这样，一个这样，一个n个顶点的图的邻接表表示由个顶点的图的邻接表表示由表头结点表头结点表表与与边表边表两部分构成。两部分构成。返回主目
29、录NoImage（1）表头结点表：）表头结点表：由所有表头结点以顺序结构（向由所有表头结点以顺序结构（向量）的形式存储，以便可以随机访问任一顶点的单量）的形式存储，以便可以随机访问任一顶点的单链表。链表。表头结点有两部分构成，其中数据域表头结点有两部分构成，其中数据域（vexdata）用于存储顶点的名或其它有关信息；链）用于存储顶点的名或其它有关信息；链域（域（firstarc）用于指向链表中第一个顶点（即与顶）用于指向链表中第一个顶点（即与顶点点vi邻接的第一个邻接点）。邻接的第一个邻接点）。表头结点结构为：表头结点结构为：vexdatafirstarc返回主目录NoImage（2）边表：由
30、表示图中顶点间邻接关系的）边表：由表示图中顶点间邻接关系的n个边链个边链表组成。它由三部分组成，表组成。它由三部分组成，其中邻接点域（其中邻接点域（adjvex）用于存放与顶点用于存放与顶点vi相邻接的顶点在图中的位置；链相邻接的顶点在图中的位置；链域（域（nextarc）用于指向与顶点）用于指向与顶点vi相关联的下一条边相关联的下一条边或弧的结点；数据域（或弧的结点；数据域（info）用于存放与边或弧相）用于存放与边或弧相关的信息（如赋权图中每条边或弧的权值等）。关的信息（如赋权图中每条边或弧的权值等）。adjvexinfonextarc弧结点结构为：弧结点结构为：返回主目录NoImage图
31、例图例 p161的图的图7.9所示是图所示是图G1、G2的邻接表表示法的邻接表表示法返回主目录NoImage邻接表存储结构的形式化说明如下：邻接表存储结构的形式化说明如下：#define MAX_VERTEX_NUM 10 /*最多顶点个数最多顶点个数*/typedef enumDG,DN,UDG,UDN GraphKind;/*图的种类图的种类*/typedef struct ArcNode int adjvex;/*该弧指向顶点的位置该弧指向顶点的位置*/struct ArcNode *nextarc;/*指向下一条弧的指针指向下一条弧的指针*/OtherInfo info;/*与该弧相关
32、的信息与该弧相关的信息*/ArcNode;返回主目录NoImagetypedef struct VertexNode VertexData data;/*顶点数据顶点数据*/ArcNode *firstarc;/*指向该顶点第一条弧的指针指向该顶点第一条弧的指针*/VertexNode;typedef struct VertexNode vertexMAX_VERTEX_NUM;int vexnum,arcnum;/*图的顶点数和弧数图的顶点数和弧数*/GraphKind kind;/*图的种类标志图的种类标志*/AdjList;/*基于邻接表的图基于邻接表的图(Adjacency List
33、Graph)*/返回主目录NoImage存储空间：存储空间：对于有对于有n个顶点，个顶点，e条边的无向图而言条边的无向图而言，若采取邻接表作为存储结构，则需要若采取邻接表作为存储结构，则需要n个表头结点个表头结点和和2e个表结点个表结点。无向图的度：无向图的度：在无向图的邻接表中，顶点在无向图的邻接表中，顶点vi的度的度恰好就是第恰好就是第i个边链表上结点的个数。个边链表上结点的个数。有向图的度：有向图的度：在有向图中，第在有向图中，第i个边链表上顶点的个边链表上顶点的个数是顶点个数是顶点vi的出度。要想求得该顶点的入度，则的出度。要想求得该顶点的入度，则必须遍历整个邻接表。在所有单链表中查找
34、邻接点必须遍历整个邻接表。在所有单链表中查找邻接点域的值为域的值为i i的结点并计数求和。的结点并计数求和。返回主目录NoImage由此可见，对于用邻接表方式存储的有向图，求顶由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，因此需要有一种解决的方法点的入度并不方便，因此需要有一种解决的方法逆邻接表法逆邻接表法。对图中的每一顶点对图中的每一顶点vi建立一个递邻接表，即对每个顶建立一个递邻接表，即对每个顶点点vi建立一个所有以顶点建立一个所有以顶点vi为弧头的弧的表，这样求为弧头的弧的表，这样求顶点顶点vi的入度即是计算逆邻接表中第的入度即是计算逆邻接表中第i个顶点的边链个顶点的边链
35、表中结点个数表中结点个数。图图G1的逆邻接表表示法见的逆邻接表表示法见p162的图的图7.10返回主目录NoImage十字链表十字链表 十字十字链表链表(Orthogonal List)是有向图的另一种链是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。接表和逆邻接表结合起来形成的一种链表。有向图中的每一条弧对应十字链表中的一个有向图中的每一条弧对应十字链表中的一个弧弧结点结点，同时有向图中的每个顶点在十字链表中对应，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做有一个结点，叫做顶点结点顶点结
36、点。这两类结点的结构见这两类结点的结构见p162的图的图7.11所示。所示。返回主目录NoImage图图G1的十字链表表示见的十字链表表示见p163的图的图7.12所示。所示。1 2 1 3 4 1 1 3 2 4 3 4 1234返回主目录NoImage建立一个有向图的十字链表的算法如下：建立一个有向图的十字链表的算法如下：void CrtOrthList（OrthList g）/*从终端输入从终端输入n个顶点的信息和个顶点的信息和e条弧的信息，以建立一个有向图的十字条弧的信息，以建立一个有向图的十字链表链表*/scanf(“%d,%d”,&n,&e);/*键盘输入图的顶点个数和弧的个数键盘
37、输入图的顶点个数和弧的个数*/for(i=0;in;i+)scanf(“%c”,g.vertexi.data）；）；g.vertexi.firstin=NULL；g.vertexi.firsout=NULL；返回主目录NoImagefor(k=0;ktailvex=i；p-headvex=j；p-tlink=g.vertexi.firstout；g.vertexi.firstout=p；p-hlink=hlink=g.vertexj.firstin.firstin；g.vertexj.firstin=p.firstin=p；/*CrtOrthList*/返回主目录NoImage十字链表的优点十
38、字链表的优点：在十字在十字链表中既能够很容易地找到以链表中既能够很容易地找到以vi为尾的为尾的弧，也能够容易地找到以弧，也能够容易地找到以vi为头的弧，因此对于有为头的弧，因此对于有向图，若采用十字链表作为存储结构，则很容易求向图，若采用十字链表作为存储结构，则很容易求出顶点出顶点vi的度。的度。返回主目录NoImage邻接多重表邻接多重表 邻接多重表邻接多重表(Adjacency Multi_list)是无向图的是无向图的另外一种存储结构。使用邻接多重表这种存储结构另外一种存储结构。使用邻接多重表这种存储结构是是因为它能够提供更为方便的边处理信息因为它能够提供更为方便的边处理信息。邻接邻接多
39、重表多重表是是指将图中关于一条边的信息用一指将图中关于一条边的信息用一个结点来表示个结点来表示。邻接多重表中的边结点结构和顶点结点结构见邻接多重表中的边结点结构和顶点结点结构见p164的图的图7.13所示。所示。返回主目录NoImage邻接多重表的结构类型说明如下：邻接多重表的结构类型说明如下：typedef struct EdgeNode int mark,ivex,jvex;struct EdgeNode *ilink,*jlink;EdgeNode;typedef struct VertexData data;EdgeNode *firstedge;VertexNode;返回主目录NoI
40、magetypedef struct VertexNode vertexMAX_VERTEX_NUM;int vexnum,arcnum;/*图的顶点数和弧数图的顶点数和弧数*/GraphKind kind;/*图的种类图的种类*/AdjMultiList;/*基于图的邻接多重表表示法基于图的邻接多重表表示法(Adjacency Multi_list)*/图图G2的邻接多重表见的邻接多重表见p165的图的图7.14所示。所示。返回主目录NoImage7.4 图的遍历图的遍历图的遍历图的遍历：从：从图中的某个顶点出发，按某种方法对图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。图
41、中的所有顶点访问且仅访问一次。为了保证图中为了保证图中的各顶点在遍历过程中访问且仅的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，用以访问一次，需要为每个顶点设一个访问标志，用以标示图中每个顶点是否被访问过，访问标志用数组标示图中每个顶点是否被访问过，访问标志用数组visitedn来表示来表示。图的遍历方法有两种：图的遍历方法有两种：深度优先搜索深度优先搜索和和广度优先搜索广度优先搜索返回主目录NoImage深度优先搜索：深度优先搜索：深度优先搜索深度优先搜索（Depth_First Search）是指按照）是指按照深度深度方向搜索方向搜索，它类似于树的先根遍历。，它类似于
42、树的先根遍历。深度优先算法的基本思想是：深度优先算法的基本思想是：（1）从图中某个顶点）从图中某个顶点v0出发，首先访问出发，首先访问v0。（2）找出刚访问过的顶点）找出刚访问过的顶点vi的第一个未被访问的邻的第一个未被访问的邻接点，然后访问该顶点。重复此步骤，直到当前的接点，然后访问该顶点。重复此步骤，直到当前的顶点没有未被访问的邻接点为止。顶点没有未被访问的邻接点为止。（3）返回前一个访问过的顶点，找出该顶点的下一返回前一个访问过的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。转个未被访问的邻接点，访问该顶点。转2。返回主目录NoImage采用递归的形式说明，采用递归的形式说明，则
43、深度优先搜索连通子图的则深度优先搜索连通子图的的基本思想可表示为：的基本思想可表示为：（1）访问出发点访问出发点v0。（2）依次）依次以以v0的未被访问的邻接点为出发点，深度的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与优先搜索图，直至图中所有与v0有路径相通的顶点有路径相通的顶点都被访问。都被访问。若此时图中还有顶点未被访问，则另选图中一若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。搜索过程，直至图中所有顶点均被访问过为止。返回主目录NoImage深度优先搜
44、索的过程示例见深度优先搜索的过程示例见p167的的7.15图所示图所示。其中实箭头代表访问方向，虚箭头代表回溯方向，其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，箭头旁边的数字代表搜索顺序，A为起始顶点。为起始顶点。8ADGBEHCFI1236710114155149131216访问序列为：访问序列为：A、B、C、F、E、G、D、H、I。返回主目录NoImage图的深度优先搜索的算法描述如下：图的深度优先搜索的算法描述如下：#define True 1#define False 0#define Error 1 /*出错出错*/#define Ok 1 int vis
45、itedMAX_VERTEX_NUM;/*访问标志数组访问标志数组*/返回主目录NoImagevoid TraverseGraphTraverseGraph(Graph g)/*对图对图g进行深度优先搜索，进行深度优先搜索，Graph 表示图的一种存储结构，如数组表表示图的一种存储结构，如数组表示法或邻接表等示法或邻接表等*/for(vi=0;vig.vexnum;vi+)visitedvi=False;/*访问标志数组初始访问标志数组初始*/for(vi=0;vig.vexnum;vi+)/*调用深度遍历连通子图的操作调用深度遍历连通子图的操作*/*若图若图g是连通图，则此循环只执行一次是连
46、通图，则此循环只执行一次*/if(！visitedvi)DepthFirstSearch(g，vi)；/*TraverseGraphTraverseGraph*/返回主目录NoImage深度遍历深度遍历v0所在地连通子图算法如下：所在地连通子图算法如下：void DepthFirstSearch（Graph g,int v0）/*深度遍历深度遍历v0所在的连通子图所在的连通子图*/visit（v0）；）；visitedv0=True；/*访问顶点访问顶点v0，并置访问标志数组相应分量值，并置访问标志数组相应分量值*/w=FirstAdjVertex(g,v0);while(w!=-1!=-1)
47、/*邻接点存在邻接点存在*/if(!visited w)DepthFirstSearch(g,w);/*递归调用递归调用DepthFirstSearch*/w=NextAdjVertex(g,v0,w);/*找下一个邻接点找下一个邻接点*/*DepthFirstSearch*/返回主目录NoImage上述算法中上述算法中对于对于FirstAdjVertex（g，v0）以及）以及NextAdjVertex（g，v0，w）并没有具体实现。）并没有具体实现。因为因为对于图的不同存储方法，两个操作的实现方法不同，对于图的不同存储方法，两个操作的实现方法不同，时间耗费也不同。时间耗费也不同。下面的算法是
48、在邻接矩阵与邻接表方式下实现上面下面的算法是在邻接矩阵与邻接表方式下实现上面算法的功能。算法的功能。返回主目录NoImage1）用邻接矩阵方式实现深度优先搜索）用邻接矩阵方式实现深度优先搜索void DepthFirstSearch(AdjMatrix g,int v0)/*图图g 为为邻接矩阵类型邻接矩阵类型AdjMatrix*/visit(v0);visitedv0=True;for(vj=0;vjadjvex)DepthFirstSearch（g，p-adjvex）；）；p=p-nextarc-nextarc；/*DepthFirstSearch*/返回主目录NoImage分析算法分析算
49、法：以邻接表作为存储结构，查找每个顶点：以邻接表作为存储结构，查找每个顶点的邻接点的时间复杂度为的邻接点的时间复杂度为O(e)，其中其中e是无向图中是无向图中的边数或有向图中弧数的边数或有向图中弧数,则深度优先搜索图的时间则深度优先搜索图的时间复杂度为复杂度为O(n+e)。返回主目录NoImage3）用非递归过程实现深度优先搜索）用非递归过程实现深度优先搜索void DepthFirstSearch(Graph g,int v0)/*从从v0出发深度优先搜索图出发深度优先搜索图g*/InitStack(S);/*初始化空栈初始化空栈*/Push(S,v0)；while(!Empty(S)v=P
50、op(S);if(!visited(v)/if(!visited(v)/*栈中可能有重复结点栈中可能有重复结点*/visit(v);visitedv=True;w=FirstAdj(g,v);/*求求v的第一个邻接点的第一个邻接点*/while(w!=-1)if(!visited(if(!visited(w)Push(S,)Push(S,w););w=NextAdj(g,=NextAdj(g,v,w);/*求求v相对于相对于w的下一个邻接点的下一个邻接点*/返回主目录NoImage7.3.2 广度优先搜索广度优先搜索广度优先搜索广度优先搜索（Breadth_First Search）是指）是指
