第七章 图 数据结构精选PPT.ppt

第七章 图 数据结构第1页，本讲稿共93页7.1 图的定义和术语图的定义和术语 （1）形式化定义）形式化定义Graph=(V,R)V=x|xdataobject /顶点的有穷非空集合顶点的有穷非空集合R=VRVR=|P(v,w)(v,wV)/两个顶点之间的关系集合两个顶点之间的关系集合（2）图形表示）图形表示图图7.1 图的示例图的示例(b)无向图无向图G2 G1 V1 V2V3V4(a)有向图有向图G1 图由结点及边图由结点及边(弧弧)组成组成,与树与树的主要区别在于的主要区别在于图可以有回路图可以有回路V3V4V5 V1 V2G2第2页，本讲稿共93页(a)有向图有向图G1 G1(V1,A1)其中：其中：V1=v1,v2,v3,v4 A1=,(b)无向图无向图G2 G2(V2,E2)其中：其中：V2=v1,v2,v3,v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)（3）相关术语）相关术语顶点顶点（Vertex）：图中的数据元素。）：图中的数据元素。弧弧（Arc）：若）：若VR，则，则表示从表示从v到到w的一条弧。的一条弧。弧尾弧尾（Tail）或初始点（）或初始点（Initial node）：弧）：弧的一个顶点的一个顶点v。弧头弧头（Head）或终端点（）或终端点（Terminal node）：弧）：弧的一个顶点的一个顶点w。有向图有向图（Digraph）：由弧和顶点组成。）：由弧和顶点组成。边边（Edge）：若）：若VR必有必有VR，即，即VR是对称的，则以是对称的，则以 无序对无序对(v,w)代替这两个有序对，表示代替这两个有序对，表示v和和w之间的一条边。之间的一条边。无向图无向图（Undigraph）：由边和顶点组成。）：由边和顶点组成。第3页，本讲稿共93页 若，用若，用n表示图中顶点数目，用表示图中顶点数目，用e表示边或弧的数目。且不考表示边或弧的数目。且不考虑顶点到其自身的边或弧，即若虑顶点到其自身的边或弧，即若VR，则，则vivj。那么，。那么，；对于有向图，；对于有向图，e的的对于无向图，对于无向图，e的取值范围是的取值范围是0到到取值范围是取值范围是0到到n(n1)。无向完全图无向完全图（Completed graph）：有）：有 条边的无向图。条边的无向图。有向完全图有向完全图：有：有n(n1)条弧的有向图。条弧的有向图。稀疏图稀疏图（Sparse graph）：有很少条边或弧（如）：有很少条边或弧（如e nlogn）的图。反之称为稠密）的图。反之称为稠密图（图（Dense graph）。）。子图子图（Subgraph）：有两个图）：有两个图G=(V,E)和和G=(V,E)，如果，如果VV且且E则称则称G为为G的子图。的子图。E,(a)图图7.1中中G1的子图的子图V1V4V1V1V1V2V4V3V3V3第4页，本讲稿共93页(b)图图7.1中中G2的子图的子图图图7.2 子图示例子图示例V1V4V1V2V4V5V3V3V1V2V1V2V4V5 对于对于无向图无向图G=(V,E)，如果边，如果边(v,v)E，则称顶点，则称顶点v和和v互为互为邻接点邻接点（Adjacent）。边）。边(v,v)依附依附（Incident）于顶点）于顶点v和和v，或者说，或者说(v,v)和顶和顶点点v和和v相关联相关联。度度：指和顶点：指和顶点v相关联的边的数目，记为相关联的边的数目，记为TD(v)。对于对于有向图有向图G=(V,A)，如果弧，如果弧A，则称顶点，则称顶点v邻接到邻接到顶点顶点v，顶点顶点v邻接自邻接自顶点顶点v。弧。弧和顶点和顶点v、v相关联。相关联。入度入度（InDegree）：以顶点）：以顶点v为头的弧的数目，记为为头的弧的数目，记为ID(v)。出度出度（OutDegree）：以顶点）：以顶点v为尾的弧的数目，记为为尾的弧的数目，记为OD(v)。有向图中，顶点有向图中，顶点v的度为的度为TD(v)ID(v)OD(v)。第5页，本讲稿共93页 一般地，如果一般地，如果顶顶点点vi的度的度记为记为TD(vi)，那么一个有，那么一个有n个个顶顶点，点，e条条边或弧的图，满足如下关系：边或弧的图，满足如下关系：路径路径（Path）：在无向图）：在无向图G=(V,E)中从顶点中从顶点v到顶点到顶点v的一个顶点序列的一个顶点序列(v=vi,0,vi,1,vi,m=v)，其中，其中(vi,j-1,vi,j)E，1jm。若。若G是有向图，则路是有向图，则路径也是有向的，顶点序列满足径也是有向的，顶点序列满足E，1jm。路径的长度路径的长度：路径上的边或弧的数目。：路径上的边或弧的数目。简单回路简单回路或或简单环简单环：除了第一个顶点和最后一个顶点之外，其余顶点不：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。重复出现的回路。回路回路或或环环（Cycle）：第一个顶点和最后一个顶点相同的路径。）：第一个顶点和最后一个顶点相同的路径。简单路径简单路径：序列中顶点不重复出现的路径。：序列中顶点不重复出现的路径。连通连通：在无向图：在无向图G中，如果从顶点中，如果从顶点v到顶点到顶点v有路径，则称有路径，则称v和和v是连通的。是连通的。连通图连通图（Connected Graph）：对于图中任意两个顶点）：对于图中任意两个顶点vi,vjV，vi和和vj都都是连通的图。是连通的图。连通分量连通分量（Connected Component）：指无向图中的极大连通子图。）：指无向图中的极大连通子图。第6页，本讲稿共93页(a)无向图无向图G3(b)G3的的3个连通分量个连通分量图图7.3 无向图及其连通分量无向图及其连通分量D E G3A BC D E F G H I K L M J G H I K A BC F J L M第7页，本讲稿共93页 强强连连通通图图：在有向：在有向图图G中，如果中，如果对对于每一于每一对对vi,vjV，vivj，从从vi到到vj和从和从vj到到vi都存在路径，都存在路径，则则称称G是是强强连连通通图图。强连通分量强连通分量：有向图中的极大强连通子图。：有向图中的极大强连通子图。生成树生成树：一个连通图的生成树是一个极小连通子图。它含有图：一个连通图的生成树是一个极小连通子图。它含有图中全部顶点，但只有足以构成一棵树的中全部顶点，但只有足以构成一棵树的n1条边。条边。图图7.4G3的最大连通分量的一棵生成树的最大连通分量的一棵生成树A BC F J L M 由生成树的定义易知：由生成树的定义易知：一棵有一棵有n个顶点的生成树有且仅有个顶点的生成树有且仅有n1条边。条边。如果一个图有如果一个图有n个顶点和小于个顶点和小于n1条边，则是非连通图。条边，则是非连通图。如果一个图有如果一个图有n个顶点和大于个顶点和大于n1条边，则一定有环。条边，则一定有环。有有n1条边的图不一定是生成树。条边的图不一定是生成树。第8页，本讲稿共93页 生成森林生成森林：一个有向图的生成森林由若干棵有向树组成，含有图：一个有向图的生成森林由若干棵有向树组成，含有图中全部的结点，但只有足以构成若干棵不相交的有向树的弧。中全部的结点，但只有足以构成若干棵不相交的有向树的弧。图图7.5一个有向图及其生成森林一个有向图及其生成森林A DF B CE A B C F E D 第9页，本讲稿共93页边的权、网图边的权、网图有时图的边或弧附带有数值信息，这种数值称为有时图的边或弧附带有数值信息，这种数值称为权权（Weight）在实际应用中，权值可以有某种含义。比如，在实际应用中，权值可以有某种含义。比如，u在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；u对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；u对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。的时间等等。每条边或弧都带权的图称为每条边或弧都带权的图称为带权图带权图或或网络网络（Network）如果边是无方向的带权图，则是一个无向网图。否则就是一个有向网图。如下图所示如果边是无方向的带权图，则是一个无向网图。否则就是一个有向网图。如下图所示是一个有向网图。是一个有向网图。第10页，本讲稿共93页（4）图的抽象数据类型定义）图的抽象数据类型定义ADT Graph 数据对象数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系R：R=VRVR=|v,wV且且P(v,w),表示从表示从v到到w的弧，的弧，谓词谓词P(v,w)定义了弧定义了弧的意义或信息的意义或信息 基本操作：基本操作：CreateGraph(&G,V,VR);初始条件：初始条件：V是图的顶点集，是图的顶点集，VR是图中弧的集合。是图中弧的集合。操作结果：按操作结果：按V和和VR的定义构造图的定义构造图G。DestroyGraph(&G);初始条件：图初始条件：图G存在。存在。操作结果：销毁图操作结果：销毁图G。第11页，本讲稿共93页LocateVex(G,u);初始条件：图初始条件：图G存在，存在，u和和G中顶点有相同特征。中顶点有相同特征。操作结果：若操作结果：若G中存在顶点中存在顶点u，则返回该顶点在图中位置；，则返回该顶点在图中位置；否则返回其他信息。否则返回其他信息。GetVex(G,v);初始条件：图初始条件：图G存在，存在，v是是G中某个顶点。中某个顶点。操作结果：返回操作结果：返回v的值。的值。PutVex(&G,v,value);初始条件：图初始条件：图G存在，存在，v是是G中某个顶点。中某个顶点。操作结果：对操作结果：对v赋值赋值value。FirstAdjVex(G,v);初始条件：图初始条件：图G存在，存在，v是是G中某个顶点。中某个顶点。操作结果：返回操作结果：返回v的第一个邻接顶点。若顶点在的第一个邻接顶点。若顶点在G中没有邻中没有邻 接顶点，则返回接顶点，则返回“空空”。第12页，本讲稿共93页 NextAdjVex(G,v,w);初始条件：图初始条件：图G存在，存在，v是是G中某个顶点，中某个顶点，w是是v的邻接点。的邻接点。操作结果：返回操作结果：返回v的（相对于的（相对于w的）下一个邻接顶点。若的）下一个邻接顶点。若w 是是v的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。InsertVex(&G,v);初始条件：图初始条件：图G存在，存在，v和图中顶点有相同特征。和图中顶点有相同特征。操作结果：在图操作结果：在图G中增添新顶点中增添新顶点v。DeleteVex(&G,v);初始条件：图初始条件：图G存在，存在，v是是G中某个顶点。中某个顶点。操作结果：删除操作结果：删除G中顶点中顶点v及其相关的弧。及其相关的弧。InsertArc(&G,v,w);初始条件：图初始条件：图G存在，存在，v和和w是是G中两个顶点。中两个顶点。操作结果：在图操作结果：在图G中增添新弧中增添新弧，若，若G是无向的，则还是无向的，则还 增添对称弧增添对称弧。DeleteArc(&G,v,w);初始条件：图初始条件：图G存在，存在，v和和w是是G中两个顶点。中两个顶点。操作结果：在图操作结果：在图G中删除弧中删除弧，若，若G是无向的，则还删是无向的，则还删 除对称弧除对称弧。第13页，本讲稿共93页 BFSTraverse(G,visit();初始条件：图初始条件：图G存在，存在，visit是顶点的应用函数。是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶操作结果：对图进行广度优先遍历。在遍历过程中对每个顶 点调用函数点调用函数Visit一次且仅一次。一旦一次且仅一次。一旦visit()失败，失败，则操作失败。则操作失败。ADT Graph DFSTraverse(G,visit();初始条件：图初始条件：图G存在，存在，visit是顶点的应用函数。是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶操作结果：对图进行深度优先遍历。在遍历过程中对每个顶 点调用函数点调用函数Visit一次且仅一次。一旦一次且仅一次。一旦visit()失败，失败，则操作失败。则操作失败。第14页，本讲稿共93页7.2 图的存储结构图的存储结构7.2.1 数组表示法（邻接矩阵）数组表示法（邻接矩阵）（1）定义）定义 数组表示法数组表示法：用两个数组分别存储数据元素（顶点）的信：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。息和数据元素之间的关系（边或弧）的信息。（2）C语言描述语言描述#defineINFINITY INT_MAX/最大值最大值#defineMAX_VERTEX_NUM 20/最大顶点个数最大顶点个数typedef enum DG,DN,UDG,UDN GraphKind;/有向图，有向网，无向图，无向网有向图，有向网，无向图，无向网typedef struct ArcCell VRTypeadj;/VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用1/或或0表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexTypevexsMAX_VERTEX_NUM;/顶点向量顶点向量 AdjMatrixarcs;/邻接矩阵邻接矩阵 intvexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 GraphKindkind;/图的种类标志图的种类标志 MGraph;第15页，本讲稿共93页思考思考设计一个算法判断一个图是否是连通图设计一个算法判断一个图是否是连通图第16页，本讲稿共93页（3）邻接矩阵中顶点度的求法）邻接矩阵中顶点度的求法 对于无向图，顶点对于无向图，顶点vi的度是邻接矩阵中第的度是邻接矩阵中第i行（或第行（或第i列）的列）的元素之和，即：元素之和，即：对于有向图，顶点对于有向图，顶点vi的出度的出度OD(vi)为第为第i行的元素之和，顶行的元素之和，顶点点vi的入度的入度ID(vi)为第为第i列的元素之和。列的元素之和。（4）网的邻接矩阵）网的邻接矩阵网的邻接矩阵可定义为：网的邻接矩阵可定义为：wi,j若若或或(vi,vj)VRAij=反之反之例如，下图列出了一个有向网和它的邻接矩阵。例如，下图列出了一个有向网和它的邻接矩阵。(b)邻接矩阵邻接矩阵(a)网网N45387 9 1 655 V1 V2 V6 V3V5V4第17页，本讲稿共93页练习1:画出下列图的邻接矩阵,并求出各顶点的度.V1V2V3V4（a）G1V1V2V3V4（b）G2第18页，本讲稿共93页练习2:绘出如下有向网络的邻接矩阵V2V4V1V3V63527948V56179=618727453A第19页，本讲稿共93页（5）图的构造）图的构造算法算法7.1如下：如下：Status CreateGraph(MGraph&G)/采用数组（邻接矩阵）表示法，构造图采用数组（邻接矩阵）表示法，构造图G。scanf(&G.kind);switch(G.kind)case DG:return CreateDG;/构造有向图构造有向图G case DN:return CreateDN;/构造有向网构造有向网G case UDG:return CreateUDG;/构造无向图构造无向图G case UDN:return CreateUDN;/构造无向网构造无向网G default:return ERROR;/CreateGraph算法算法7.1是在邻接矩阵存储结构是在邻接矩阵存储结构MGraph上对图的构造操上对图的构造操作的实现框架，它根据图作的实现框架，它根据图G的种类调用具体构造算法。的种类调用具体构造算法。第20页，本讲稿共93页 Status CreateUDN(MGraph&G)/采用数组（邻接矩阵）表示法，构造无向网采用数组（邻接矩阵）表示法，构造无向网G。scanf(&G.vexnum,&G.arcnum,&IncInfo);/IncInfo为为0则各弧不含其他信息则各弧不含其他信息for(i=0;i G.vexnum;+i)scanf(&G.vexsi);/构造顶点向量构造顶点向量for(i=0;i G.vexnum;+i)/初始化邻接矩阵初始化邻接矩阵for(j=0;j G.vexnum;+j)G.arcsij=INFINITY,NULL;/adj,infofor(k=0;k G.arcnum;+k)/构造邻接矩阵构造邻接矩阵scanf(&v1,&v2,&w);/输入一条边依附的顶点及权值输入一条边依附的顶点及权值i=LocateVex(G,v1);/确定确定v1和和v2在在G中位置中位置j=LocateVex(G,v2);G.arcsij.adj=w;/弧弧的权值的权值if(IncInfo)Input(*G.arcsij.info);/若弧含有相关信息，则输入若弧含有相关信息，则输入G.arcsji=G.arcsij;/置置的对称弧的对称弧/forreturn OK;/CreateUDN算法算法7.2如下：如下：算法算法7.2构造一个具有构造一个具有n个顶点和个顶点和e条边的无向网条边的无向网G。其时间复杂度为。其时间复杂度为O(n2+e*n)，其中对邻接矩，其中对邻接矩阵阵G.arcs的初始化耗费了的初始化耗费了O(n2)的时间。的时间。第21页，本讲稿共93页7.2.2 邻接表邻接表（1）定义）定义 邻接表邻接表（Adjacency List）：是图的一种链式存储结构。在）：是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的个单链表中的结点表示依附于顶点结点表示依附于顶点vi的边（对有向图是以顶点的边（对有向图是以顶点vi为尾的弧）。为尾的弧）。逆邻接表逆邻接表：即对每个顶点：即对每个顶点vi建立一个链接以建立一个链接以vi为头的弧的表。为头的弧的表。在逆邻接表中可以方便的确定顶点的入度或以顶点在逆邻接表中可以方便的确定顶点的入度或以顶点vi为头的弧。为头的弧。（2）结点结构）结点结构头结点头结点 data firstarc表结点表结点 adjvex nextarc info表结点由表结点由3个域组成：个域组成：adjvex：邻接点域，指示与顶点：邻接点域，指示与顶点vi邻接的点在图中的位置。邻接的点在图中的位置。nextarc：链域，指示下一条边或弧的结点。：链域，指示下一条边或弧的结点。info：数据域，存储和边或弧相关的信息，如权值等。：数据域，存储和边或弧相关的信息，如权值等。头结点由头结点由2个域组成：个域组成：data：数据域，存储顶点：数据域，存储顶点vi的名或其他有关信息。的名或其他有关信息。firstarc：链域，指向链表中第一个结点。：链域，指向链表中第一个结点。表头结点通常以顺表头结点通常以顺序结构的形式存储，序结构的形式存储，以便随机访问任一以便随机访问任一顶点的链表。顶点的链表。第22页，本讲稿共93页#defineMAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息顶点信息 struct ArcNode *firstarc;/指向第一条依附该顶点的弧的指针指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 kind kind;/图的种类标志图的种类标志 ALGraph;（3）C语言描述语言描述第23页，本讲稿共93页（4）图形表示）图形表示(a)有向图有向图 和无向图和无向图 G1G2G1V1 V2V3 V4G2V1 V2V4 V5V3 (b)G1的邻接表的邻接表V1V2V3V40 1 2 3 2 1 30V1V2V3V40 1 2 3 2003(c)G1的逆邻接表的逆邻接表第24页，本讲稿共93页 (d)G2的邻接表的邻接表图图7.6 邻接表和逆邻接表邻接表和逆邻接表对于无向图，顶点对于无向图，顶点vi的度恰为第的度恰为第i个链表中的结点数。个链表中的结点数。对于有向图，顶点对于有向图，顶点vi的出度的出度OD(vi)为第为第i个链表中的结点个数；求顶点个链表中的结点个数；求顶点vi的的 入度入度ID(vi)必须遍历整个邻接表，查找所有链表中其邻接点域的值为必须遍历整个邻接表，查找所有链表中其邻接点域的值为i的结点，的结点，它们的总和即为顶点它们的总和即为顶点vi的入度。的入度。（5）邻接表中顶点度的求法）邻接表中顶点度的求法V1V2V3V40 1 2 3 V54 3 1 2 1 2 0 4 2 4 3 1 0 G2V1 V2V4 V5V3第25页，本讲稿共93页练习3:画出下列图的邻接表与逆邻接表,并求出各顶点的度.V1V2V3V4（a）G1V1V2V3V4（b）G2v3v2v13201v42310（a）G1的邻接表data20firstarcv3v2v13201v412333（b）G2的邻接表data firstarc第26页，本讲稿共93页练习3:画出下列图的邻接表与逆邻接表,并求出各顶点的度.V1V2V3V4（a）G1V1V2V3V4（b）G2v3v2v13201v401200（c）G2的逆邻接表datafirstarc第27页，本讲稿共93页7.2.3 十字链表（有向图）十字链表（有向图）（1）定义）定义 十字链表十字链表（Orthogonal List）：是有向图的另一种链式存储结构。可）：是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上头相同的弧在同一链表上，弧尾相同的弧也在同一链表上（2）结点结构）结点结构弧结点弧结点头结点（顶点结点）头结点（顶点结点）data firstin firstouttailvex headvex hlink tlink info 弧结点由弧结点由5个域组成：个域组成：tailvex：尾域，指示弧尾顶点在图中的位置。：尾域，指示弧尾顶点在图中的位置。headvex：头域，指示弧头顶点在图中的位置。：头域，指示弧头顶点在图中的位置。hlink：链域，指向弧头相同的下一条弧。：链域，指向弧头相同的下一条弧。tlink：链域，指向弧尾相同的下一条弧。：链域，指向弧尾相同的下一条弧。info：数据域，指向该弧的相关信息。：数据域，指向该弧的相关信息。头结点由头结点由3个域组成：个域组成：data：数据域，存储和顶点相关的信息，如顶点名称等。：数据域，存储和顶点相关的信息，如顶点名称等。firstin：链域，指向以该顶点为弧头的第一个弧结点。：链域，指向以该顶点为弧头的第一个弧结点。firstout：链域，指向以该顶点为弧尾的第一个弧结点。：链域，指向以该顶点为弧尾的第一个弧结点。第28页，本讲稿共93页#defineMAX_VERTEX_NUM 20typedef struct ArcBox int tailvex,headvex;/该弧的尾和头顶点的位置该弧的尾和头顶点的位置 struct ArcBox *hlink,*tlink;/分别为弧头相同和弧尾相同的弧的链域分别为弧头相同和弧尾相同的弧的链域 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data;ArcBox *firstin,*firstout;/分别指向该顶点第一条入弧和出弧分别指向该顶点第一条入弧和出弧 VexNode;typedef struct VexNodexlistMAX_VERTEX_NUM;/表头向量表头向量 intvexnum,arcnum;/有向图的当前顶点数和弧数有向图的当前顶点数和弧数 OLGraph;（3）C语言描述语言描述第29页，本讲稿共93页（4）图形表示）图形表示图图7.7有向图的十字链表有向图的十字链表V1 V2 (a)V3 V4 V1(b)0 1V2 1 V3 2 V4 3 0 2 2 0 3 0 2 3 3 1 3 2 0 第30页，本讲稿共93页（5）图的构造）图的构造 Status CreateDG(OLGraph&G)/采用十字链表存储表示，构造有向图采用十字链表存储表示，构造有向图G(G.kind=DG)。scanf(&G.vexnum,&G.arcnum,&IncInfo);/IncInfo为为0则各弧不含其他信息则各弧不含其他信息for(i=0;i G.vexnum;+i)/构造表头向量构造表头向量 scanf(&G.xlisti.data);/输入顶点值输入顶点值 G.xlisti.firstin=NULL;/初始化指针初始化指针 G.xlisti.firstout=NULL;for(k=0;k info);/若弧含有相关信息，则输入若弧含有相关信息，则输入/for /CreateDG算法算法7.3如下：如下：第31页，本讲稿共93页7.2.4 邻接多重表（无向图）邻接多重表（无向图）（1）定义）定义 邻接多重表邻接多重表（Adjacency Multilist）：是无向图的另一种链式）：是无向图的另一种链式存储结构。邻接多重表的结构和十字链表类似。在邻接多重表中，存储结构。邻接多重表的结构和十字链表类似。在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附两个所有依附于同一顶点的边串联在同一链表中，由于每条边依附两个顶点，则每个边结点同时链接在两个链表中。顶点，则每个边结点同时链接在两个链表中。（2）结点结构）结点结构顶点顶点结结点点data firstedgemark ivex ilink jvex jlink info边结点边结点 边结点由边结点由6个域组成：个域组成：mark：标志域，用以标记该条边是否被搜索过。：标志域，用以标记该条边是否被搜索过。ivex和和jvex：为该边依附的两个顶点在图中的位置。：为该边依附的两个顶点在图中的位置。ilink：链域，指向下一条依附于顶点：链域，指向下一条依附于顶点ivex的边。的边。jlink：链域，指向下一条依附于顶点：链域，指向下一条依附于顶点jvex的边。的边。info：数据域，指向和边相关的各种信息的指针域。：数据域，指向和边相关的各种信息的指针域。顶点结点有顶点结点有2个域组成：个域组成：data：数据域，存储和该顶点相关的信息。：数据域，存储和该顶点相关的信息。firstedge：链域，指示第一条依附于该顶点的边。：链域，指示第一条依附于该顶点的边。在邻接多重表中在邻接多重表中,每一条边每一条边用一个结点表示用一个结点表示,每一个顶每一个顶点也用一个结点表示。点也用一个结点表示。第32页，本讲稿共93页（3）C语言描述语言描述#defineMAX_VERTEX_NUM 20typedef emnu unvisited,visited VisitIf;typedef struct EBox VisitIf mark;/访问标记访问标记 int ivex,jvex;/该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox *ilink,*jlink;/分别指向依附这两个顶点的下一条边分别指向依附这两个顶点的下一条边 InfoType *info;/该边信息指针该边信息指针 EBox;typedef struct VexBox VertexType data;EBox *firstedge;/指向指向第一条依附第一条依附该顶点的边该顶点的边 VexBox;typedef struct VexBoxadjmulistMAX_VERTEX_NUM;intvexnum,edgenum;/无向图的当前顶点数和边数无向图的当前顶点数和边数 AMLGraph;第33页，本讲稿共93页（4）图形表示）图形表示G2V1 V2V4 V5V3图图7.8无向图无向图G2的邻接多重表的邻接多重表4V1 0 1V2 1 V3 2 V4 3 0 V5 0 3 2 1 2 3 4 1 2 4第34页，本讲稿共93页7.3 图的遍历图的遍历7.3.1 深度优先遍历深度优先遍历 图的遍历图的遍历（Traversing Graph）：从图中某一顶点出发，）：从图中某一顶点出发，访遍图中其余顶点，且使每一个顶点仅被访问一次的过程。访遍图中其余顶点，且使每一个顶点仅被访问一次的过程。（1）定义）定义 深度优先遍历（深度优先遍历（Depth_First Search）类似于树的先根遍历，）类似于树的先根遍历，是树的先根遍历的推广。是树的先根遍历的推广。主要思想主要思想：假设初始状态是图中所有顶点未曾被访问，则深度优先：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点搜索可从图中某个顶点v出发，访问此顶点，然后依次从出发，访问此顶点，然后依次从v的未被访问的的未被访问的邻接点出发深度优先遍历图，直至图中所有和邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。第35页，本讲稿共93页（2）深度优先搜索遍历图的过程演示）深度优先搜索遍历图的过程演示以图以图7.9(a)中无向图中无向图G4为例，深度优先搜索遍历图。为例，深度优先搜索遍历图。(b)深度优先搜索的过程深度优先搜索的过程(a)无向图无向图 图图7.9 遍历图的过程遍历图的过程 G4V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8112573482 说明说明：假设从：假设从v1出发进行搜索，在访问了顶点出发进行搜索，在访问了顶点v1之后，选择邻接点之后，选择邻接点v2。因为。因为v2未曾访问，则从未曾访问，则从v2成分进行搜索。依次类推，接着从成分进行搜索。依次类推，接着从v4，v8，v5出发进行搜索。出发进行搜索。在访问了在访问了v5之后，由于之后，由于v5的邻接点都已被访问，则搜索回到的邻接点都已被访问，则搜索回到v8。同理，搜索继续。同理，搜索继续回到回到v4，v2直至直至v1，此时由于，此时由于v1的另一个邻接点未被访问，则搜索又从的另一个邻接点未被访问，则搜索又从v1到到v3，再，再继续进行下去。得到的顶点访问序列为：继续进行下去。得到的顶点访问序列为：第36页，本讲稿共93页（3）遍历算法）遍历算法 /-算法算法7.4和和7.5使用的全局变量使用的全局变量-Boolean visitedMAX;/访问标志数组访问标志数组Status(*VisitFunc)(int v);/函数变量函数变量算法算法7.5如下：如下：void DFS(Graph G,int v)/从第从第v个顶点出发递归地深度优先遍历图个顶点出发递归地深度优先遍历图G。visitedv=TRUE;VisitFunc(v);/访问第访问第v个顶点个顶点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对对v尚未访问的邻接顶点尚未访问的邻接顶点w递归调用递归调用DFS 算法算法7.4如下：如下：void DFSTraverse(Graph G,Status(*Visit)(int v)/对图对图G作深度优先遍历作深度优先遍历 VisitFunc=Visit;/使用全局变量使用全局变量VisitFunc,使使DFS不必设函数指针参数不必设函数指针参数 for(v=0;v G.vexnum;+v)visitedv=FALSE;/访问标志数组初始化访问标志数组初始化 for(v=0;v G.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用对尚未访问的顶点调用DFS G3A BC D E F G H I K L M J 第37页，本讲稿共93页7.3.2 广度优先遍历广度优先遍历（1）定义）定义 广度优先遍历（广度优先遍历（Breadth_First Search）类似于树的按层次遍历的过程。）类似于树的按层次遍历的过程。主要思想主要思想：假设从图中某顶点：假设从图中某顶点v出发，在访问了出发，在访问了v之后依次访问之后依次访问v的各个未的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使使“先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问，直至被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。所有顶点都被访问到为止。（2）广度优先搜索遍历图的过程演示）广度优先搜索遍历图的过程演示 以图以图7.9(a)中无向图为例，广度优先搜索遍历图。中无向图为例，广度优先搜索遍历图。第38页，本讲稿共93页V1V2V3V4V5V6V7V8图图7.10 广度优先搜索的过程广度优先搜索的过程 说明说明：假设从：假设从v1出发进行搜索。首先访问出发进行搜索。首先访问v1和和v1的邻接点的邻接点v2和和v3，然后依，然后依次访问次访问v2的邻接点的邻接点v4和和v5及及v3的邻接点的邻接点v6和和v7，最后访问，最后访问v4的邻接点的邻接点v8。由于。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的遍历。遍历。得到的顶点访问序列为：得到的顶点访问序列为：G4V1V2V3V4V5V6V7V8第39页，本讲稿共93页 void BFSTraverse(Graph G,Status(*Visit)(int v)/按广度优先非递归遍历图按广度优先非递归遍历图G。使用辅助队列。使用辅助队列Q和访问标志数组和访问标志数组visited。for(v=0;v G.vexnum;+v)visitedv=FALSE;InitQueue(Q);/置空的辅助队列置空的辅助队列Qfor(v=0;v=0;w=NextAdjVex(G,u,w)if(!Visitedw)/w为为u的尚未访问的邻接顶点的尚未访问的邻接顶点 visitedw=TRUE;Visit(w);EnQueue(Q,w