1、8.1 图的基本概念图的基本概念第第8章章 图图8.2 图的存储结构图的存储结构8.3 图的遍历图的遍历8.4 生成树和最小生成树生成树和最小生成树8.5 最短路径最短路径8.6 拓扑排序拓扑排序8.7 AOE网与关键路径网与关键路径本章小结本章小结8.1 图的基本概念图的基本概念8.1.1 图的定义图的定义 图（图（Graph）G由两个集合由两个集合V（vertex）和）和E（Edge）组成，记为组成，记为G=(V，E)，其中，其中V是顶点的有限集合，记为是顶点的有限集合，记为V(G)，E是连接是连接V中两个不同顶点（顶点对）的边的有限集中两个不同顶点（顶点对）的边的有限集合，记为合，记为E
2、(G)。和和离散数学离散数学中采用的方法相同，通过顶点集和边集中采用的方法相同，通过顶点集和边集来表示一个图的逻辑结构，实际上就是二元组表示。来表示一个图的逻辑结构，实际上就是二元组表示。在图在图G中，如果代表边的顶点对是无序的，则称中，如果代表边的顶点对是无序的，则称G为为无向无向图图，无向图中代表边的无序顶点对通常用圆括号括起来，用，无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。以表示一条无向边。如果表示边的顶点对是有序的，则称如果表示边的顶点对是有序的，则称G为为有向图有向图，在有向，在有向图中代表边的顶点对通常用尖括号括起来图中代表边的顶点对通常用尖括号括起来。说明
3、：说明：对于对于n个顶点的图，对每个顶点连续编号，即顶个顶点的图，对每个顶点连续编号，即顶点的编号为点的编号为0n-1。通过编号唯一确定一个顶点。通过编号唯一确定一个顶点。8.1.2 图的基本术语图的基本术语 1.端点和邻接点端点和邻接点 在一个无向图中，若存在一条边在一个无向图中，若存在一条边(i，j)，则称顶点，则称顶点i和顶点和顶点j为此边的两个端点，为此边的两个端点，并称它们互为并称它们互为邻接点邻接点。在一个有向图中，若存在一条边在一个有向图中，若存在一条边，则称此边是顶点，则称此边是顶点i的一条出边，同时的一条出边，同时也是顶点也是顶点j的一条入边；称顶点的一条入边；称顶点i和顶点
4、和顶点j分别为此边的起始端点（简称为起点）分别为此边的起始端点（简称为起点）和终止端点（简称终点）；称顶点和终止端点（简称终点）；称顶点i 和和顶点顶点j 互为互为邻接点邻接点。13024(a)13024(b)2.顶点的度、入度和出度顶点的度、入度和出度 在无向图中，顶点所具有的边的数在无向图中，顶点所具有的边的数目称为该目称为该顶点的度顶点的度。在有向图中，以顶点在有向图中，以顶点i为终点的入边为终点的入边的数目，称为该的数目，称为该顶点的入度顶点的入度。以顶点。以顶点i为为始点的出边的数目，称为该始点的出边的数目，称为该顶点的出度顶点的出度。一个顶点的入度与出度的和为该一个顶点的入度与出度
5、的和为该顶点的顶点的度度。若一个图中有若一个图中有n个顶点和个顶点和e条边，每条边，每个顶点的度为个顶点的度为di（1in），则有：），则有：niide12113024(a)13024(b)例例一个无向连通图中有一个无向连通图中有16条边，所有顶点的度均小于条边，所有顶点的度均小于5，度为度为4的顶点有的顶点有3个，度为个，度为3的顶点有的顶点有4个，度为个，度为2的顶点有的顶点有2个，个，则该图有则该图有 个顶点。个顶点。A.10B.11C.12D.13解：解：设该图有设该图有n个顶点，图中度为个顶点，图中度为i的顶点数为的顶点数为ni（0i4），显），显然然n0=0，n=3+4+2+n1+
6、n0=9+n1，而度之和，而度之和=43+34+22+n1=28+n1，而度之和，而度之和=2e=32，所以有，所以有28+n1=32，得，得n1=4，n=9+n1=13。本题答案为。本题答案为D。3.完全图完全图 若无向图中的每两个顶点之间都存若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此间都存在着方向相反的两条边，则称此图为图为完全图完全图。显然，完全无向图包含有条边，完显然，完全无向图包含有条边，完全有向图包含有全有向图包含有n(n-1)条边。例如，图条边。例如，图(a)所示的图是一个具有所示的图是一个
7、具有4个顶点的完全个顶点的完全无向图，共有无向图，共有6条边。图条边。图(b)所示的图是所示的图是一个具有一个具有4个顶点的完全有向图，共有个顶点的完全有向图，共有12条边。条边。(b)10231023(a)4.稠密图、稀疏图稠密图、稀疏图 当一个图接近完全图时，则称当一个图接近完全图时，则称为稠密图。相反，当一个图含有为稠密图。相反，当一个图含有较少的边数（即当较少的边数（即当en(n-1)）时，）时，则称为则称为稀疏图稀疏图。5.子图子图 设 有 两 个 图设 有 两 个 图 G=(V，E)和和G=(V，E)，若，若V是是V的子集，的子集，即即V V，且，且E是是E的子集，即的子集，即E
8、E，则称，则称G是是G的的子图子图。例如。例如图图(b)是图是图(a)的子图，而图的子图，而图(c)不是不是图图(a)的子图。的子图。(a)1302413024(b)13024(c)注意：注意：G中中V的子集和的子集和E的子集并的子集并不一定构成不一定构成G的子图。的子图。6.路径和路径长度路径和路径长度 在一个图在一个图G=(V，E)中，从顶点中，从顶点i到顶点到顶点j的一条路径是一个顶点序列的一条路径是一个顶点序列(i,i1,i2,im,j)，若此图若此图G是无向图，则边是无向图，则边(i,i1)，(i1,i2)，(im-1,im)，(im,j)属于属于E(G)；若此图是有向图，；若此图是
9、有向图，则则，属于属于E(G)。路径长度路径长度是指一条路径上经过的边的数是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为同外，其余顶点均不相同，则称此路径为简简单路径单路径。例如，有图中，。例如，有图中，(0，2，1)就是一条就是一条简单路径，其长度为简单路径，其长度为2。1023 7.回路或环回路或环 若一条路径上的开始点与结束若一条路径上的开始点与结束点为同一个顶点，则此路径被称为点为同一个顶点，则此路径被称为回路或环。开始点与结束点相同的回路或环。开始点与结束点相同的简单路径被称为简单路径被称为简
10、单回路简单回路或或简单环简单环。例如，右图中，例如，右图中，(0，2，1，0)就就是一条简单回路，其长度为是一条简单回路，其长度为3。1023 8.连通、连通图和连通分量连通、连通图和连通分量 在无向图在无向图G中，若从顶点中，若从顶点i到顶点到顶点j有路径，则称顶点有路径，则称顶点i和和j是是连通连通的。的。若图若图G中任意两个顶点都中任意两个顶点都连通，则称连通，则称G为为连通图连通图，否则，否则称为称为非连通图非连通图。无向图无向图G中的极大连通子中的极大连通子图称为图称为G的连通分量。显然，的连通分量。显然，任何连通图的连通分量只有一任何连通图的连通分量只有一个，即本身，而非连通图有多
11、个，即本身，而非连通图有多个个连通分量连通分量。1023102(b)(a)3 9.强连通图和强连通分量强连通图和强连通分量 在有向图在有向图G中，若从顶点中，若从顶点i到到顶点顶点j有路径，则称从顶点有路径，则称从顶点i到到j是是连通连通的。的。若图若图G中的任意两个顶点中的任意两个顶点i和和j都连通，即从顶点都连通，即从顶点i到到j和从顶点和从顶点j到到i都存在路径，则称图都存在路径，则称图G是是强连强连通图通图。有向图有向图G中的极大强连通子图中的极大强连通子图称为称为G的的强连通分量强连通分量。显然，强。显然，强连通图只有一个强连通分量，即连通图只有一个强连通分量，即本身，非强连通图有多
12、个强连通本身，非强连通图有多个强连通分量。分量。1023(b)(a)102310.权和网权和网 图中每一条边都可以附有一个对应的数值，这种与图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为边相关的数值称为权权。权可以表示从一个顶点到另一个。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为顶点的距离或花费的代价。边上带有权的图称为带权图，带权图，也称作也称作网网。例例8.1 有有n个顶点的有向强连通图最多需要多少条边？个顶点的有向强连通图最多需要多少条边？最少需要多最少需要多 少条边？少条边？解：解：有有n个顶点的有向强连通图最多有个顶点的有向强连通图最多有n(
13、n-1)条边条边（构成一个有向完全图的情况）；最少有（构成一个有向完全图的情况）；最少有n条边（条边（n个个顶点依次首尾相接构成一个环的情况）。顶点依次首尾相接构成一个环的情况）。012n-2n-18.2 图的存储结构图的存储结构 8.2.1 邻接矩阵存储方法邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有是具有n（n0）个顶点的图，）个顶点的图，顶点的顺序依次为顶点的顺序依次为0n-1，则则G的邻接矩阵的邻接矩阵A是是n阶方阵，其定义如下：阶方阵，其定义如下：（1）如果）如果G是无向图，则：是无向图，则：Aij=1：若：若
14、(i,j)E(G)0:其他其他 （2）如果）如果G是有向图，则：是有向图，则：Aij=1：若：若E(G)0:其他其他（3）如果）如果G是带权无向图，则：是带权无向图，则：Aij=wij：若：若ij且且(i,j)E(G)0：i=j ：其他：其他（4）如果）如果G是带权有向图，则：是带权有向图，则：Aij=wij：若：若ij且且E(G)0：i=j：其他：其他注意：注意：带权图和不带权图表示的元素类型不同。带权图带权图和不带权图表示的元素类型不同。带权图（不论有向还是无向图）（不论有向还是无向图）Aij用用double表示，不带权图表示，不带权图（不论有向还是无向图）（不论有向还是无向图）Aij用用
15、int表示。表示。011011011111010011011101001001000001100001100010101320413204A10 1 2 3 401234A20 1 2 3 401234对称对称不对称不对称思考题：思考题：（1）对于有）对于有n个顶点个顶点e条边的无向图，邻接矩阵表示时条边的无向图，邻接矩阵表示时有多少个元素，多少个非有多少个元素，多少个非0元素？元素？（2）对于有）对于有n个顶点个顶点e条边的有向图，邻接矩阵表示时条边的有向图，邻接矩阵表示时有多少个元素，多少个非有多少个元素，多少个非0元素？元素？邻接矩阵的特点如下：邻接矩阵的特点如下：（1）图的邻接矩阵表示
16、是唯一的。）图的邻接矩阵表示是唯一的。（2）无向图的邻接矩阵一定是一个对称矩阵。因此，）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。（或下）三角形阵的元素即可。（3）不带权的有向图的邻接矩阵一般来说是一个稀疏）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，因此，当图的顶点较多时，可以采用三元组表的方矩阵，因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。法存储邻接矩阵。（4）对于无向图，邻接矩阵的第）对于无向图，邻接矩阵的第i行（或第行（或第i列）非零元列）
17、非零元素（或非素（或非元素）的个数正好是第元素）的个数正好是第i个顶点的度。个顶点的度。（5）对于有向图，邻接矩阵的第）对于有向图，邻接矩阵的第i行（或第行（或第i列）非零元列）非零元素（或非素（或非元素）的个数正好是第元素）的个数正好是第i个顶点的出度（或入度）。个顶点的出度（或入度）。（6）用邻接矩阵方法存储图，很容易确定图中任意两个）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很必须按行、按列对每个元素进行检测，所花费的时间代价很大。这
18、是用邻接矩阵存储图的局限性。大。这是用邻接矩阵存储图的局限性。邻接矩阵的数据类型定义如下：邻接矩阵的数据类型定义如下：#define MAXV typedef struct int no;/顶点编号顶点编号 InfoType info;/顶点其他信息顶点其他信息 VertexType;/顶点类型顶点类型typedef struct /图的定义图的定义 int edgesMAXVMAXV;/邻接矩阵邻接矩阵 int n，e;/顶点数，弧数顶点数，弧数 VertexType vexsMAXV;/存放顶点信息存放顶点信息 MGraph;/图的邻接矩阵表示类型图的邻接矩阵表示类型8.2.2 邻接表存储
19、方法邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式分配相结合图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中，对图中每个顶点建立一个单链表，的存储方法。在邻接表中，对图中每个顶点建立一个单链表，第第i个单链表中的节点表示依附于顶点个单链表中的节点表示依附于顶点i的边（对有向图是以顶的边（对有向图是以顶点点i为尾的边）。每个单链表上附设一个表头节点。为尾的边）。每个单链表上附设一个表头节点。边表节点边表节点 表头节点表头节点adjvexnextarcinfodatafirstarctypedef struct ANode int adjvex;/该边的终点编号该边的
20、终点编号 struct ANode*nextarc;/指向下一条边的指针指向下一条边的指针 InfoType info;/该边的相关信息该边的相关信息 ArcNode;/边表节点类型边表节点类型typedef struct Vnode Vertex data;/顶点信息顶点信息 ArcNode*firstarc;/指向第一条边指向第一条边 VNode;/邻接表头节点类型邻接表头节点类型typedef VNode AdjListMAXV;/AdjList是邻接表类型是邻接表类型typedef struct AdjList adjlist;/邻接表邻接表 int n,e;/图中顶点数图中顶点数n和
21、边数和边数e ALGraph;/完整的图邻接表类型完整的图邻接表类型 其中，表节点由三个域组成，其中，表节点由三个域组成，adjvex指示与顶点指示与顶点i邻邻接的点在图中的位置，接的点在图中的位置，nextarc指示下一条边或弧的节点，指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。存储与边或弧相关的信息，如权值等。表头节点由两个域组成，表头节点由两个域组成，data存储顶点存储顶点i的名称或其的名称或其他信息，他信息，firstarc指向链表中第一个节点。指向链表中第一个节点。1320413204data firstarcadjvex next表头节点表头节点边表节点边表
22、节点思考题：思考题：（1）对于有）对于有n个顶点个顶点e条边的无向图，邻接表表示时有条边的无向图，邻接表表示时有多少个表头节点，多少个表节点？多少个表头节点，多少个表节点？（2）对于有）对于有n个顶点个顶点e条边的有向图，邻接表表示时有条边的有向图，邻接表表示时有多少个表头节点，多少个表节点？多少个表头节点，多少个表节点？邻接表的特点如下：邻接表的特点如下：（1）邻接表表示不唯一。这是因为在每个顶点对应的单链）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。的算法以
23、及边的输入次序。（2）对于有）对于有n个顶点和个顶点和e条边的无向图，其邻接表有条边的无向图，其邻接表有n个顶个顶点节点和点节点和2e个边节点。显然，在总的边数小于个边节点。显然，在总的边数小于n(n-1)/2的情况下，的情况下，邻接表比邻接矩阵要节省空间。邻接表比邻接矩阵要节省空间。（3）对于无向图，邻接表的顶点）对于无向图，邻接表的顶点i对应的第对应的第i个链表的边节个链表的边节点数目正好是顶点点数目正好是顶点i的度。的度。（4）对于有向图，邻接表的顶点）对于有向图，邻接表的顶点i对应的第对应的第i个链表的边节个链表的边节点数目仅仅是顶点点数目仅仅是顶点i的出度。其入度为邻接表中所有的出度
24、。其入度为邻接表中所有adjvex域值域值为为i的边节点数目。的边节点数目。例例8.2 给定一个具有给定一个具有n个节点的无向图的邻接矩阵和邻接表。个节点的无向图的邻接矩阵和邻接表。（1）设计一个将邻接矩阵转换为邻接表的算法；）设计一个将邻接矩阵转换为邻接表的算法；（2）设计一个将邻接表转换为邻接矩阵的算法；）设计一个将邻接表转换为邻接矩阵的算法；（3）分析上述两个算法的时间复杂度。）分析上述两个算法的时间复杂度。解：解：（1）在邻接矩阵上查找值不为）在邻接矩阵上查找值不为0的元素，找到这样的的元素，找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法元素后创建一个表节点并在邻接表
25、对应的单链表中采用前插法插入该节点。算法如下：插入该节点。算法如下：void MatToList(MGraph g，ALGraph*&G)/将邻接矩阵将邻接矩阵g转换成邻接表转换成邻接表G int i，j，n=g.eexnum;ArcNode*p;/n为顶点数为顶点数 G=(ALGraph*)malloc(sizeof(ALGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;i=0;j-)if(g.edgesij!=0)p=(ArcNode*)malloc(sizeof(ArcNode);/创建节点创建节点*p p-adjvex=j;p-nextarc
26、=G-adjlisti.firstarc;/将将*p链到链表头链到链表头 G-adjlisti.firstarc=p;G-n=n;G-e=g.e;（2）在邻接表上查找相邻节点，找到后修改相应邻接矩阵）在邻接表上查找相邻节点，找到后修改相应邻接矩阵元素的值。算法如下：元素的值。算法如下：void ListToMat(ALGraph*G，MGraph&g)int i，j，n=G-n;ArcNode*p;for(i=0;iadjlisti.firstarc;while(p!=NULL)g.edgesip-adjvex=1;p=p-nextarc;g.n=n;g.e=G-e;（3）算法）算法1的时间复
27、杂度均为的时间复杂度均为O(n2)。算法。算法2的时间的时间复杂度为复杂度为O(n+e)，其中，其中e为图的边数。为图的边数。图的邻接矩阵的操作图的邻接矩阵的操作 利用邻接矩阵定义的数据结构，可以方便地实现图的利用邻接矩阵定义的数据结构，可以方便地实现图的各种操作。各种操作。(1)图的创建图的创建AdjGraph *Create_Graph(MGraph*G)printf(“请输入图的种类标志：请输入图的种类标志：”);scanf(“%d”,&G-kind);G-vexnum=0;/*初始化顶点个数初始化顶点个数 */return(G);(2)图的顶点定位图的顶点定位 图的顶点定位操作实际上是
28、确定一个顶点在图的顶点定位操作实际上是确定一个顶点在vexs数数组中的位置组中的位置(下标下标)，其过程完全等同于在顺序存储的线，其过程完全等同于在顺序存储的线性表中查找一个数据元素。性表中查找一个数据元素。算法实现：算法实现：int LocateVex(MGraph*G,VexType*vp)int k;for(k=0;kvexnum;k+)if(G-vexsk=*vp)return(k);return(-1);/*图中无此顶点图中无此顶点 */(3)向图中增加顶点向图中增加顶点 向图中增加一个顶点的操作，类似在顺序存储的线性表的末向图中增加一个顶点的操作，类似在顺序存储的线性表的末尾增加一
29、个数据元素。尾增加一个数据元素。算法实现：算法实现：int AddVertex(MGraph*G,VexType*vp)int k,j;if (G-vexnum=MAX_VEX)printf(“Vertex Overflow!n”);return(-1);if (LocateVex(G,vp)!=-1)printf(“Vertex has existed!n”);return(-1);k=G-vexnum;G-vexsG-vexnum+=*vp;if(G-kind=DG|G-kind=AG)for(j=0;jvexnum;j+)G-adjjk.ArcVal=G-adjkj.ArcVal=0;/
30、*是不带权的有向图或无向图是不带权的有向图或无向图 */elsefor(j=0;jvexnum;j+)G-adjjk.ArcVal=INFINITY;G-adjkj.ArcVal=INFINITY;/*是带权的有向图或无向图是带权的有向图或无向图 */return(k);(4)向图中增加一条弧向图中增加一条弧 根据给定的弧或边所依附的顶点，修改邻接矩阵中所对应的根据给定的弧或边所依附的顶点，修改邻接矩阵中所对应的数组元素。数组元素。算法实现：算法实现：int AddArc(MGraph*G,ArcType*arc)int k,j;k=LocateVex(G,&arc-vex1);j=Locat
31、eVex(G,&arc-vex1);if(k=-1|j=-1)printf(“Arcs Vertex do not existed!n”);return(-1);if(G-kind=DG|G-kind=WDG)G-adjkj.ArcVal=arc-ArcVal;G-adjkj.ArcInfo=arc-ArcInfo;/*是有向图或带权的有向图是有向图或带权的有向图*/else G-adjkj.ArcVal=arc-ArcVal;G-adjjk.ArcVal=arc-ArcVal;G-adjkj.ArcInfo=arc-ArcInfo;G-adjjk.ArcInfo=arc-ArcInfo;/*
32、是无向图或带权的无向图是无向图或带权的无向图,需对称赋值需对称赋值 */return(1);利用邻邻接链链表存储结构储结构描述，可方便地实现图实现图的基本操作。(1)图图的创创建ALGraph*Create_Graph(ALGraph*G)printf(“请输请输入图图的种类标种类标志：”);scanf(“%d”,&G-kind);G-vexnum=0;/*初始化顶顶点个数个数 */return(G);(2)图的顶点定位图的顶点定位 图的顶点定位实际上是确定一个顶点在图的顶点定位实际上是确定一个顶点在AdjList数数组中的某个元素的组中的某个元素的data域内容。域内容。算法实现：算法实现：
33、int LocateVex(ALGraph*G,VexType*vp)int k;for(k=0;kvexnum;k+)if(G-AdjListk.data=*vp)return(k);return(-1);/*图中无此顶点图中无此顶点 */(3)向图中增加顶点向图中增加顶点 向图中增加一个顶点的操作，在向图中增加一个顶点的操作，在AdjList数组的末尾增加一个数组的末尾增加一个数据元素。数据元素。算法实现：算法实现：int AddVertex(ALGraph*G,VexType*vp)int k,j;if (G-vexnum=MAX_VEX)printf(“Vertex Overflow!
34、n”);return(-1);if (LocateVex(G,vp)!=-1)printf(“Vertex has existed!n”);return(-1);G-AdjListG-vexnum.data=*vp;G-AdjListG-vexnum.degree=0;G-AdjListG-vexnum.firstarc=NULL;k=+G-vexnum;return(k);(4)向图中增加一条弧向图中增加一条弧 根据给定的弧或边所依附的顶点，修改单链表：无向图修改根据给定的弧或边所依附的顶点，修改单链表：无向图修改两个单链表；有向图修改一个单链表。两个单链表；有向图修改一个单链表。算法实现：
35、算法实现：int AddArc(ALGraph*G,ArcType*arc)int k,j;LinkNode*p,*q;k=LocateVex(G,&arc-vex1);j=LocateVex(G,&arc-vex2);if(k=-1|j=-1)printf(“Arcs Vertex do not existed!n”);return(-1);p=(LinkNode*)malloc(sizeof(LinkNode);p-adjvex=arc-vex1;p-info=arc-info;p-nextarc=NULL;/*边的起始表结点赋值边的起始表结点赋值 */q=(LinkNode*)mallo
36、c(sizeof(LinkNode);q-adjvex=arc-vex2;q-info=arc-info;q-nextarc=NULL;/*边的末尾表结点赋值边的末尾表结点赋值 */if(G-kind=AG|G-kind=WAG)q-nextarc=G-adjlistk.firstarc;G-adjlistk.firstarc=q;p-nextarc=G-adjlistj.firstarc;G-adjlistj.firstarc=p;/*是无向图是无向图,用头插入法插入到两个单链表用头插入法插入到两个单链表 */else /*建立有向图的邻接链表建立有向图的邻接链表,用头插入法用头插入法 */
37、q-nextarc=G-adjlistk.firstarc;G-adjlistk.firstarc=q;/*建立正邻接链表用建立正邻接链表用*/q-nextarc=G-adjlistj.firstarc;/G-adjlistj.firstarc=q;/*建立逆邻接链表用建立逆邻接链表用*/return(1);十字链表法十字链表法 十字链链表(Orthogonal List)是有向图图的另一种链种链式存储结构储结构，是将将有向图图的正邻邻接表和逆邻邻接表结结合起来来得到的一种链种链表。在这种结构这种结构中，每条条弧的弧头结头结点和弧尾结结点都存放在链链表中，并将并将弧结结点分别组织别组织到以弧尾
38、结结点为头为头(顶顶点)结结点和以弧头结头结点为头为头(顶顶点)结结点的链链表中。这这种结构种结构的结结点逻辑结构逻辑结构如图图7-12所示。弧结点弧结点tailvex headvex info hlink tlink顶点结顶点结点点Data firstin firstout图图7-12 十字链表结点结构十字链表结点结构 data域：存储和顶点相关的信息；域：存储和顶点相关的信息；指针域指针域firstin：指向以该顶点为弧头的第一条弧：指向以该顶点为弧头的第一条弧所对应的弧结点；所对应的弧结点；指针域指针域firstout：指向以该顶点为弧尾的第一条弧：指向以该顶点为弧尾的第一条弧所对应的弧
39、结点；所对应的弧结点；尾域尾域tailvex：指示弧尾顶点在图中的位置；：指示弧尾顶点在图中的位置；头域头域headvex：指示弧头顶点在图中的位置；：指示弧头顶点在图中的位置；指针域指针域hlink：指向弧头相同的下一条弧；：指向弧头相同的下一条弧；指针域指针域tlink：指向弧尾相同的下一条弧；：指向弧尾相同的下一条弧；Info域：指向该弧的相关信息；域：指向该弧的相关信息；结点类型定义结点类型定义#define INFINITY MAX_VAL /*最大值值*/#define MAX_VEX 30 /最大顶顶点数数 typedef struct ArcNode int tailvex,h
40、eadvex;/尾结结点和头结头结点在图图中的位置InfoType info ;/与与弧相关关的信息,如权值权值struct ArcNode *hlink,*tlink;ArcNode;/*弧结结点类类型定义义 */typedef struct VexNode VexType data;/顶顶点信息ArcNode *firstin,*firstout;VexNode;/*顶顶点结结点类类型定义义 */typedef struct int vexnum;VexNode xlistMAX_VEX;OLGraph;/*图图的类类型定义义 */下图图所示是一个个有向图图及其十字链链表(略去了表结结点的
41、info域)。从这种从这种存储结构图储结构图可以看出，从从一个顶个顶点结结点的firstout出发发，沿表结结点的tlink指针构针构成了正邻邻接表的链链表结构结构，而从从一个顶个顶点结结点的firstin出发发，沿表结结点的hlink指针构针构成了逆邻邻接表的链链表结构结构。V V0 0V V1 1V V2 2V V3 30 10 2 2 02 3 3 0 3 1 3 2 0213V0V1 V2V3有向图的十字链表结构有向图的十字链表结构邻接多重表邻接多重表 邻邻接多重表(Adjacency Multilist)是无向图图的另一种链种链式存储结构储结构。邻邻接表是无向图图的一种种有效的存储结
42、构储结构，在无向图图的邻邻接表中，一条边条边(v,w)的两个两个表结结点分别别初选选在以v和w为头结为头结点的链链表中，很容易求得顶顶点和边边的信息，但在涉及到边边的操作会带来会带来不便。邻邻接多重表的结构结构和十字链链表类类似，每条边条边用一个结个结点表示；邻邻接多重表中的顶顶点结结点结构与邻结构与邻接表中的完全相同，而表结结点包括六个个域如图图7-14所示。data firstedge顶点结点顶点结点图图7-14 邻接多重表的结点结构邻接多重表的结点结构表结点表结点mark ivex jvex info ilink jlink Data域：存储和顶点相关的信息；域：存储和顶点相关的信息；指
43、针域指针域firstedge：指向依附于该顶点的第一条边：指向依附于该顶点的第一条边所对应的表结点；所对应的表结点；标志域标志域mark：用以标识该条边是否被访问过；：用以标识该条边是否被访问过；ivex和和jvex域：分别保存该边所依附的两个顶点域：分别保存该边所依附的两个顶点在图中的位置；在图中的位置；info域：保存该边的相关信息；域：保存该边的相关信息；指针域指针域ilink：指向下一条依附于顶点：指向下一条依附于顶点ivex的边；的边；指针域指针域jlink：指向下一条依附于顶点：指向下一条依附于顶点jvex的边；的边；结结点类类型定义义#define INFINITY MAX_VA
44、L /*最大值值*/#define MAX_VEX 30 /*最大顶顶点数数 */typedef emnu unvisited,visited Visitting;typedef struct EdgeNode Visitting mark;/访问标记访问标记int ivex,jvex ;/该边该边依附的两个结两个结点在图图中的位置InfoType info ;/与边与边相关关的信息,如权值权值struct EdgeNode *ilink,*jlink;/分别别指向依附于这两个顶这两个顶点的下一条边条边EdgeNode;/*弧边结边结点类类型定义义 */typedef struct VexNo
45、de VexType data;/顶顶点信息ArcNode *firsedge;/指向依附于该顶该顶点的第一条边条边VexNode;/*顶顶点结结点类类型定义义 */typedef struct int vexnum;VexNode mullistMAX_VEX;AMGraph;下图图所示是一个个无向图图及其邻邻接多重表。邻邻接多重表与邻与邻接表的区别区别：后者的同一条边条边用两个两个表结结点表示，而前者只用一个个表结结点表示；除标标志域外，邻邻接多重表与邻与邻接表表达达的信息是相同的，因此，操作的实现实现也基本相似。图图7-15 无向图及其多重邻接链表无向图及其多重邻接链表v1v2v3v4v
46、1v2v3v40123 0 1 0 2 2 1 2 3 0 3图的边表存储结构图的边表存储结构 在某些应应用中，有时时主要考察图图中各个边个边的权值权值以及所依附的两个顶两个顶点，即图图的结构结构主要由边来边来表示，称为边称为边表存储结构储结构。在边边表结构结构中，边边采用顺顺序存储储，每个边个边元素由三部分组组成：边边所依附的两个顶两个顶点和边边的权值权值；图图的顶顶点用另一个顺个顺序结结构构的顶顶点表存储储。如图图所示。边边表存储结构储结构的形式描述如下：#define INFINITY MAX_VAL /*最大值值*/#define MAX_VEX 30 /*最大顶顶点数数 */#def
47、ine MAX_EDGE 100 /*最大边数边数 */typedef struct ENode int ivex,jvex ;/*边边所依附的两个顶两个顶点 */WeightType weight ;/*边边的权值权值 */ENode;/*边边表元素类类型定义义 */typedef struct int vexnum,edgenum;/*顶顶点数数和边数边数 */VexType vexlistMAX_VEX;/*顶顶点表 */ENode edgelistMAX_EDGE;/*边边表 */ELGraph;无向图的边表表示无向图的边表表示v0v2v4v3v1674239 8顶点表顶点表v0v1v
48、2v3v401234边边 表表1 3 21 4 92 3 82 4 33 4 40 2 70 1 68.3 图的遍历图的遍历8.3.1 图的遍历的概念图的遍历的概念 从给定图中任意指定的顶点（称为初始点）出发，按照某从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的种搜索方法沿着图的边访问图中的所有顶点所有顶点，使，使每个顶点仅被每个顶点仅被访问一次访问一次，这个过程称为，这个过程称为图的遍历图的遍历。如果给定图是连通的无向。如果给定图是连通的无向图或者是强连通的有向图，则遍历过程一次就能完成，并可按图或者是强连通的有向图，则遍历过程一次就能完成，并可按访问的先后
49、顺序得到由该图所有顶点组成的一个序列。访问的先后顺序得到由该图所有顶点组成的一个序列。根据搜索方法的不同，图的遍历方法有两种：一种叫做深根据搜索方法的不同，图的遍历方法有两种：一种叫做深度优先搜索法（度优先搜索法（DFS）；另一种叫做广度优先搜索法（）；另一种叫做广度优先搜索法（BFS）。）。深度优先搜索遍历的过程是：深度优先搜索遍历的过程是：（1）从图中某个初始顶点）从图中某个初始顶点v出发，首先访问初始顶点出发，首先访问初始顶点v。（2）选择一个与顶点）选择一个与顶点v相邻且没被访问过的顶点相邻且没被访问过的顶点w为初始为初始顶点，再从顶点，再从w出发进行深度优先搜索，直到图中与当前顶点出
50、发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。邻接的所有顶点都被访问过为止。8.3.2 深度优先搜索遍历深度优先搜索遍历以邻接表为存储结构的深度优先搜索遍历算法如下以邻接表为存储结构的深度优先搜索遍历算法如下（其中，（其中，v是初始顶点编号，是初始顶点编号，visited是一个全局数组，初是一个全局数组，初始时所有元素均为始时所有元素均为0表示所有顶点尚未访问过）：表示所有顶点尚未访问过）：体现出后进先出的特点：用栈或递归方式实现。体现出后进先出的特点：用栈或递归方式实现。vwvoid DFS(ALGraph*G，int v)ArcNode*p;int w;visite
