数据结构 第六章 图.ppt

《数据结构 第六章 图.ppt》由会员分享，可在线阅读，更多相关《数据结构 第六章 图.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章图1本章要点本章要点n图的概念及有关术语；图的概念及有关术语；n图的表示和存储实现图的表示和存储实现邻接矩阵、邻接表、十字链表邻接矩阵、邻接表、十字链表和邻接多重表；和邻接多重表；n图的遍历图的遍历深度优先遍历、广度优先遍历，以及图的深度优先遍历、广度优先遍历，以及图的连通性；连通性；n最小生成树最小生成树MSTMST性质及性质及Prim(Prim(普里姆普里姆)算法、算法、Kruskal(Kruskal(克鲁斯卡尔克鲁斯卡尔)算法；算法；n最短路径最短路径Dijkstra(Dijkstra(迪杰斯特拉迪杰斯特拉)算法和算法和Floyd(Floyd(弗洛弗洛伊德伊德)算法；算法；n

2、拓朴排序与关键路径拓朴排序与关键路径AOEAOE网、关键活动、关键路径网、关键活动、关键路径2图是一种比线性表和树更复杂的非线性结构。图是一种比线性表和树更复杂的非线性结构。在在人人工工智智能能、工工程程施施工工、数数学学、物物理理、化化学学、生生物物和和计算机等领域中都有广泛的应用。计算机等领域中都有广泛的应用。一对一关系一对一关系树树形形结结构构：数数据据元元素素之之间间的的关关系系有有着着层层次次关关系系,即即一一个个结点对上有唯一的双亲结点对上有唯一的双亲,对下可有多个孩子对下可有多个孩子 一对多关系一对多关系图图：结结点点之之间间的的联联系系是是任任意意的的,即即图图中中任任何何两两

3、个个结结点点都都可能相关可能相关多对多关系多对多关系线线性性表表：数数据据元元素素之之间间仅仅有有线线性性关关系系,即即每每个个元元素素只只有有一个直接前驱和一个直接后继一个直接前驱和一个直接后继36.1 图的基本概念图的基本概念(1)(1)图是由顶点的非空有限集合是由顶点的非空有限集合V V和与边的集合和与边的集合E E组组成，记为：成，记为：G=(V G=(V，E)E)其中：其中：V=vV=vi i|0|0 i i n,nn,n 0,v0,vi i VertxType VertxType；E=(v E=(vi i,v,vj j)|v)|vi i,v,vj j V,V,且且P(vP(vi i

4、,v,vj j).).(2)(2)顶点:(3)(3)无向图：如有：如有(v(vi i,v,vj j)E E，必有，必有(v(vj j,v,vi i)E E，即关，即关系系E E中顶点偶对是无序的。中顶点偶对是无序的。边：无序偶对，：无序偶对，(v(vi i,v,vj j)(4)(4)有向图：如有：如有(v(vi i,v,vj j)E E，仅表示从顶点，仅表示从顶点v vi i到到v vj j的的一条边，即关系一条边，即关系E E中顶点偶对是有序的。中顶点偶对是有序的。弧：有序偶对，：有序偶对，v 弧尾：弧头：4(5)(5)用用n n表示顶点的数目表示顶点的数目,用用e e表示边表示边/弧的数目

5、弧的数目,则：则：无向图边数有无向图边数有:0:0至至n(n-1)/2 n(n-1)/2 有向图的弧数有有向图的弧数有:0:0至至n(n-1)n(n-1)完全图：有向完全图：(6)(6)权：边或弧有关的信息，代表与应用背景有关的边或弧有关的信息，代表与应用背景有关的特定数值或代价。特定数值或代价。网：每条边上都带权的图：每条边上都带权的图5(7)(7)子图:若有两个图若有两个图G=(V,E),GG=(V,E),G1 1=(V=(V1 1,E,E1 1),),如果如果V V1 1 V,V,且且E E1 1 E,(E,(且且E E1 1中顶点在中顶点在V V1 1中中),),则称为则称为G G1

6、1为为G G的子图。的子图。(8)(8)稀疏图:稠密图：(9)无向图中：无向图中：邻接点:相关联：度：TD(v)有向图中：有向图中：相关联：入度：ID(v)出度：OD(v)度：TD(v)=？6(10)(10)路径：无向图：无向图G=(V,E)G=(V,E)中中,从顶点从顶点p p到到q q的路径的路径:(p=v (p=v0 0,v,v1 1,v,vk k=p),=p),其中其中(v(vi i,v,vi+1i+1)E,0ik-1;E,0ik-1;对于有向图对于有向图G=(V,A),G=(V,A),从顶点从顶点p p到到q q的路径的路径:(p=v (p=v0 0,v,v1 1,v,vk k=p)

7、,=p),其中其中v E,0ik-1;E,0ik-1;路径的长度:路径上的边或弧的数目路径上的边或弧的数目 简单路径:顶点不重复出现的路径顶点不重复出现的路径 回路或环:第一个顶点和最后一个顶点相同的路径第一个顶点和最后一个顶点相同的路径 简单回路或环:(11)(11)连通图:连通分量:强连通图:强连通分量:7(12)(12)生成树:注意注意:有有n-1n-1条边的图不一定就是生成树条边的图不一定就是生成树 生成森林:有向树:(13)(13)顶点在图中的位置:8ABLKFEHGIJCDHIFECABLKGJD连通分量与生成树示意图连通分量与生成树示意图HIABLKGJDFECGa)b)c)d)

8、e)f)96.2 6.2 图的表示和存储实现方法图的表示和存储实现方法 n一、图的抽象数据类型定义ADT Graph ADT Graph 数据对象数据对象V:V:具有相同特性的数据元素的集合具有相同特性的数据元素的集合,称为顶点集。称为顶点集。数据关系数据关系R R：R=|v,wV R=|v,wV且且p(v,w),p(v,w),表示从表示从v v到到w w的弧的弧,谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息 基本操作基本操作：InitiateGraph(&G InitiateGraph(&G）；）；/初始化图的存储空间初始化图的存储空间 操作结果：初始化图操作结果

9、：初始化图G G DestroyGraph(&G)DestroyGraph(&G)；/销毁，释放图的存储空间销毁，释放图的存储空间 初始条件：图初始条件：图G G存在存在 操作结果：销毁图操作结果：销毁图G G ADT Graph ADT Graph 图中任意两个顶点之间都可能存在联系，不能用数据元素在图中任意两个顶点之间都可能存在联系，不能用数据元素在存储区的物理位置表示元素之间的关系；图中各结点的度不同，存储区的物理位置表示元素之间的关系；图中各结点的度不同，而且可能差别还比较大。而且可能差别还比较大。10二、邻接距阵存储（数组表示法）用一个一维数组存储顶点的信息；用一个一维数组存储顶点的

10、信息；用另一个二维数组存储边或弧的信息用另一个二维数组存储边或弧的信息(邻接矩阵邻接矩阵)假假设设图图G G=(V(V，E)E)有有n n个个顶顶点点V V=vv1 1,v v2 2,v vn n。则不带权值的边值信息的则不带权值的边值信息的AijAij可以表示为可以表示为:在实际存储时考虑到无向图的邻接矩阵的对称性在实际存储时考虑到无向图的邻接矩阵的对称性,可可采用压缩的方式只存储矩阵的下三角或上三角元素。采用压缩的方式只存储矩阵的下三角或上三角元素。aij=1 vi adj vj0 vi nadj vj(Or,i=j)11#define INFINITY INT_MAX /#define

11、INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /#define MAX_VERTEX_NUM 20 /最大顶点个数最大顶点个数typedef enum DG,DN,AG,ANGraphKind;typedef enum DG,DN,AG,ANGraphKind;/有向图有向图,有向网有向网,无向图无向图,无向网无向网 typedef struct ArcCeltypedef struct ArcCel VRType adj;/VRType VRType adj;/VRType是顶点关系类型。是顶点关系类型。/对无权图对无权图,用用1 1或或

12、0 0表示相邻否；对带权图表示相邻否；对带权图,则为权值类型。则为权值类型。InfoType *Info;/InfoType *Info;/该弧相关信息的指针该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structtypedef struct VertexType vexsMAX_VERTEX_NUM;/VertexType vexsMAX_VERTEX_NUM;/顶点向量顶点向量 AdjMatrix arcs;/AdjM

13、atrix arcs;/邻接矩阵邻接矩阵 int vexnum,arcnum;/int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数 GraphKind kind;/GraphKind kind;/图的种类标志图的种类标志Mgraph;Mgraph;图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示:12ACDBEF(a)无向图ACDBE(b)有向图13对对于于加加权权图图(网网)，邻邻接接矩矩阵阵定定义义为为：A=aA=aijij nnnn可可以以表表示为示为:ACBD加权图加权图31549=4154919353A14v1v6v2v3v4v55487956513特

14、点特点:1:1）无向图的邻接矩阵一定是一个对称矩阵，可按前面压缩）无向图的邻接矩阵一定是一个对称矩阵，可按前面压缩存储方法存储存储方法存储 2)2)不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，可采不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，可采用三元组方法存储邻接矩阵；用三元组方法存储邻接矩阵；3)3)对于无向图，邻接矩阵的第对于无向图，邻接矩阵的第i i行（或第行（或第i i列）非零元素（或非列）非零元素（或非 元素元素）的个数正好是第）的个数正好是第i i个顶点的度个顶点的度TDTD（vi)vi)4)4)对于有向图，邻接矩阵的第对于有向图，邻接矩阵的第i i行（或第行（或第i i列

15、）非零元素（或非列）非零元素（或非 元素元素）的个数正好是第）的个数正好是第i i个顶点的出度个顶点的出度OD(vi)(OD(vi)(或入试或入试ID(vi)ID(vi)5)5)用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连，但是要确定图中有多少条边，则必须按行、是否有边相连，但是要确定图中有多少条边，则必须按行、列对每个元素进行检测，所花费的时间代价很大。列对每个元素进行检测，所花费的时间代价很大。5 7 4 8 9 5 6 5 3 1 A=V=V=V V1 1V V2 2V V3 3V V4 4V V5 5v v6 61

16、5三、邻接表存储结构n是一种顺序存储与链式存储相结合的存储方法。是一种顺序存储与链式存储相结合的存储方法。n一个图的邻接表由两个部分组成：一个图的邻接表由两个部分组成：顶点信息用一维数组存储顶点信息用一维数组存储每每个个顶顶点点建建立立一一个个单单链链表表，用用来来存存储储该该顶顶点点的的所所有有邻邻接接点点。链链接接与与vi有有边边相相连连的的顶顶点点(无无向向图图)；或或从从vi出出发发到到达达的的顶顶点点(有向图有向图)。邻邻接接表表存存储储可可以以看看成成是是对对邻邻接接距距阵阵的的改改进进-去去掉掉0元元素素，增加指针增加指针adjvex weightnextarc链链结点结点顶点顶

17、点结点结点vertex firstarc 16各链表的头结点通常以顺序结构的形式存储。各链表的头结点通常以顺序结构的形式存储。如下如下无向图无向图G1G1的的邻接表邻接表表示表示如下如下:17如下如下有向图有向图G G2 2的的邻接表邻接表表示表示如下如下:18n对无向图对无向图 n n个顶点个顶点,e,e条边条边,则它的邻接表需则它的邻接表需n n个头结点和个头结点和2e2e个链结点个链结点;顶点顶点v vi i的度恰为第的度恰为第i i链表中链表中的结点的个数链表中链表中的结点的个数;n对有向图对有向图第第i i个链表中结点个数只是个链表中结点个数只是v vi i的出度的出度;为求其入度为

18、求其入度,要遍历整要遍历整个邻接表。个邻接表。为了方便对有向图为了方便对有向图,再建一个再建一个逆邻接表,即即v vi i为弧头的弧构成为弧头的弧构成的链表。相对于逆邻接表，把有向图的邻接表称为的链表。相对于逆邻接表，把有向图的邻接表称为正邻接表。G2G2的逆邻接表如下所示。的逆邻接表如下所示。19n在在邻邻接接表表上上,容容易易找找到到任任一一顶顶点点的的第第一一个个邻邻接接顶顶点点和和下下一一个个邻邻接接顶顶点点,但但要要判判断断v vi i和和v vj j之之间间是是否否有有边边或或弧弧相连相连,则要搜索第则要搜索第i i个或第个或第j j个链表。个链表。n建建立立邻邻接接表表或或逆逆邻

19、邻接接表表时时,若若输输入入的的顶顶点点信信息息即即为为顶顶点点的的编编号号,则则建建立立邻邻接接表表的的时时间间复复杂杂度度为为O(n+e),O(n+e),否否则则通通过过查查找找才才能能得得到到顶顶点点在在图图中中的的位位置置,则则时时间间复复杂杂度为度为O(n*e)O(n*e)20typedef struct ArcNode/typedef struct ArcNode/邻接点的结点结构邻接点的结点结构(弧的结点结构弧的结点结构)intint adjvex;adjvex;/邻接的顶点的下标邻接的顶点的下标unsigned intunsigned intweight;/weight;/弧的

20、权值弧的权值struct ArcNode*nextarc;/struct ArcNode*nextarc;/下一条弧的指针下一条弧的指针ArcNode,*ArcLink;ArcNode,*ArcLink;typedef struct VexNode /typedef struct VexNode /顶点的结点结构顶点的结点结构VexTypeVexTypedata;data;/顶点数据顶点数据boolboolvisited;/visited;/顶点的访问标志，用于图的遍历顶点的访问标志，用于图的遍历ArcLinkArcLinkfirstarc;/firstarc;/第一条弧的指针第一条弧的指针V

21、exNode,*VexLink;VexNode,*VexLink;typedef struct ArcListGraph /typedef struct ArcListGraph /图的结构图的结构VexNode VexNode*vex;*vex;/顶点存储空间的基地址顶点存储空间的基地址int int vexnum;/vexnum;/顶点个数顶点个数int int vexsize;/vexsize;/顶点个数最大值顶点个数最大值int int arcnum;/arcnum;/边的条数边的条数unsigned char kind;/unsigned char kind;/图的种类或用图的种类或

22、用 GraphKind GraphKind ALGraph;ALGraph;图的邻接表存储表示：21部分操作实现：部分操作实现：（1 1）初始化操作。初始化图，给定能存储的顶点个）初始化操作。初始化图，给定能存储的顶点个数的最大值，为顶点分配存储空间。数的最大值，为顶点分配存储空间。Status InitGraph(ALGraph&G,int n)Status InitGraph(ALGraph&G,int n)if(n 1)if(n 1)return FALSE;return FALSE;G.vex=new VexNoden;G.vex=new VexNoden;if(!G.vex)if(!

23、G.vex)return FALSE;return FALSE;G.vexnum=0;G.vexnum=0;G.arcnum=0;G.arcnum=0;G.vexsize=n;G.vexsize=n;return TRUE;return TRUE;/InitGraph/InitGraph22(2)(2)销毁操作。销毁所有顶点及邻接链表结点的空间。销毁操作。销毁所有顶点及邻接链表结点的空间。void DestroyGraph(ALGraph&G)void DestroyGraph(ALGraph&G)for(i=0;iG.vexnum;i+)/for(i=0;inextarc;p=p-nexta

24、rc;delete q;delete q;delete G.vex;delete G.vex;/释放顶点的存储空间释放顶点的存储空间 G.vex=0;G.vex=0;G.vexnum=0;G.vexnum=0;G.vexsize=0;G.vexsize=0;/DestroyGraph/DestroyGraph23(3)(3)插入顶点。在顶点向量中查找，如果没有则插入顶点。插入顶点。在顶点向量中查找，如果没有则插入顶点。Status InsertVextex(ALGraph&G,VexType v)Status InsertVextex(ALGraph&G,VexType v)if(G.vexn

25、um=G.vexsize)if(G.vexnum=G.vexsize)return ERROR;/return ERROR;/顶点的存储空间已满，则返回错误顶点的存储空间已满，则返回错误if(LocateVex(G,v)=0)if(LocateVex(G,v)=0)/v/v已经在顶点集中已经在顶点集中 return OK;return OK;G.vexG.vexnum.data=v;/G.vexG.vexnum.data=v;/在顶点集中，添加顶点在顶点集中，添加顶点G.vexG.vexnum.firstarc=0;G.vexG.vexnum.firstarc=0;G.vexnum+;G.ve

26、xnum+;return OK;return OK;/InsertVextex/InsertVextex 24(4)(4)查找顶点的位置。在图查找顶点的位置。在图G G中，查找顶点中，查找顶点v v的位置，若的位置，若G G中存在中存在顶点顶点v v，则返回该顶点的下标；否则返回，则返回该顶点的下标；否则返回-1-1。int LocateVex(ALGraph&G,VexType v)int LocateVex(ALGraph&G,VexType v)for(i=0;i G.vexnum;i+)for(i=0;i adjvex=n2)if(p-adjvex=n2)find=true;p-wei

27、ght=weight;break;find=true;p-weight=weight;break;p=p-nextarc;p=p-nextarc;if(!find)if(!find)q=new ArcNode;q=new ArcNode;if(!q)if(!q)return ERROR;return ERROR;q-adjvex=n2;q-adjvex=n2;q-weight=weight;p=G.vexn1.firstarc;q-weight=weight;p=G.vexn1.firstarc;q-nextarc=p;G.vexn1.firstarc=q;q-nextarc=p;G.vexn

28、1.firstarc=q;return OK;return OK;/InsertArc/InsertArc26(7)(7)输出图。输出图的所有顶点，以及顶点的所有邻接点输出图。输出图的所有顶点，以及顶点的所有邻接点void PrintGraph(ALGraph&G)void PrintGraph(ALGraph&G)for(i=0;i G.vexnum;i+)for(i=0;i adjvex.data);adjvex.data);p=p-nextarc;p=p-nextarc;printf(n);printf(n);/PrintGraph/PrintGraph 27(8)(8)创建图。从键盘输

29、入图的顶点和边，创建图创建图。从键盘输入图的顶点和边，创建图void CreateGraph(ALGraph&G)void CreateGraph(ALGraph&G)while(1)while(1)printf(printf(输入顶点：输入顶点：););fflush(stdin);fflush(stdin);scanf(%c,&v1);scanf(%c,&v1);if(LocateVex(G,v1)=-1)InsertVextex(G,v1);if(LocateVex(G,v1)=-1)InsertVextex(G,v1);printf(printf(继续输入？继续输入？(Y/N);fflu

30、sh(stdin);ch=getchar();(Y/N);fflush(stdin);ch=getchar();if(ch!=Y&ch!=y)if(ch!=Y&ch!=y)break;break;while(1)while(1)printf(printf(输入边的第输入边的第1 1个顶点：个顶点：););fflush(stdin);fflush(stdin);scanf(%c,&v1);scanf(%c,&v1);printf(printf(输入边的第输入边的第2 2个顶点：个顶点：););fflush(stdin);fflush(stdin);scanf(%c,&v2);scanf(%c,&

31、v2);if(InsertArc(G,v1,v2)printf(if(InsertArc(G,v1,v2)printf(插入成功插入成功n);n);else else printf(printf(插入失败插入失败n);n);printf(printf(继续输入？继续输入？(Y/N);fflush(stdin);ch=getchar();(Y/N);fflush(stdin);ch=getchar();if(ch!=Y&ch!=y)if(ch!=Y&ch!=y)break;break;PrintGraph(G);PrintGraph(G);/CreateGraph/CreateGraph28四、

32、十字链表存储结构有向图的表示其中其中:弧结点结构中弧结点结构中tailvex,headvex分别指示弧尾和弧头两个顶分别指示弧尾和弧头两个顶点在图中的序号点在图中的序号;headlink指向弧头相同的下一条弧指向弧头相同的下一条弧;taillink指向指向弧尾相同的下一条弧弧尾相同的下一条弧;info为指向该弧的相关信息。为指向该弧的相关信息。顶点结点中顶点结点中vertex存放和顶点相关的信息存放和顶点相关的信息;firstin和和firstout分别指分别指向该顶点为弧头或弧尾的第一个弧结点。向该顶点为弧头或弧尾的第一个弧结点。tailvex headvex taillink弧结点弧结点顶

33、点结点顶点结点vertex firstin headlink infofirstout十字链表是是将有向图的将有向图的正正邻接表和逆邻接表结合起邻接表和逆邻接表结合起来得到的一种链表。来得到的一种链表。每一条弧对应一个弧结点每一条弧对应一个弧结点,每个顶点对应一个顶点结点每个顶点对应一个顶点结点,结结点结构如下点结构如下:29ADCB有向图的十字链表有向图的十字链表存储结构存储结构ABCD3 00 11 22 33 10123 a)b)30typedef struct ArcNode /typedef struct ArcNode /弧的结点结构弧的结点结构intint tailvextail

34、vex，headvex;/headvex;/弧头和弧尾两个顶点的位置弧头和弧尾两个顶点的位置struct ArcNode struct ArcNode*taillink*taillink，*headlink;headlink;/下一条相同弧头、弧尾的弧的指针下一条相同弧头、弧尾的弧的指针ArcNode,*ArcLink;ArcNode,*ArcLink;typedef struct VexNode /typedef struct VexNode /顶点的结点结构顶点的结点结构VexType data;/VexType data;/顶点数据顶点数据boolboolvisited;/visited

35、;/顶点的访问标志，用于图的遍历顶点的访问标志，用于图的遍历ArcLink firstinArcLink firstin，firstout;/firstout;/指向第一条入弧、出弧的指针指向第一条入弧、出弧的指针VexNode,*VexLink;VexNode,*VexLink;typedef struct ArcListGraph /typedef struct ArcListGraph /图的结构图的结构VexNode *vex;VexNode *vex;/顶点存储空间的基地址顶点存储空间的基地址int int vexnum;/vexnum;/顶点个数顶点个数int int vexsiz

36、e;/vexsize;/顶点个数最大值顶点个数最大值int int arcnum;/arcnum;/边的条数边的条数unsigned char unsigned char kind;kind;/图的种类图的种类 ALGraph;ALGraph;有向图的十字链表存储结构定义：31n无无向向图图的的链链式式存存储储表表示示,实实际际是是对对邻邻接接表表的的改改进进。在在无无向向图图的的邻邻接接表表中中,一一条条边边(v(vi i,v,vj j),),对对应应两两个个结结点点,分分别别在在第第i i个个和和第第j j个个链中链中,这样在对边的操作比较麻烦。这样在对边的操作比较麻烦。n邻接多重表邻接多

37、重表,即让每一条边中用一个结点表示即让每一条边中用一个结点表示,这个结点同时链这个结点同时链在两个链表中在两个链表中,它的结构如下所示它的结构如下所示:ivexilink链链结点结点 (边边)顶点结点顶点结点(表头结点表头结点)datafirstedgejvexinfojlink其中其中:ivex,jvex:ivex,jvex为该边依附的两个顶点在图中的位置为该边依附的两个顶点在图中的位置;ilink ilink指向下一条依附于顶点指向下一条依附于顶点ivexivex的边的边,jlink jlink指向下一条依附于顶点指向下一条依附于顶点jvexjvex的边的边;info info为指向和边相

38、关的各种信息的指针域。为指向和边相关的各种信息的指针域。每个顶点用一个结点表示每个顶点用一个结点表示,其中其中datadata存储和该顶点相关的信息存储和该顶点相关的信息,firstedgefirstedge指示第一条依附于该顶点的边。指示第一条依附于该顶点的边。如下图所示如下图所示:五、邻接多重表存储结构32ADCB无无向图的向图的多重邻接存储结构多重邻接存储结构ABCD0 10 31 22 33 10123 a)b)33typedef struct EdgNode /typedef struct EdgNode /边的结点结构边的结点结构intint ivex ivex，jvex;/jve

39、x;/边两个邻接顶点的位置边两个邻接顶点的位置struct EdgNode struct EdgNode*ilink*ilink，*jlink;*jlink;/分别指向下一条与分别指向下一条与ilinkilink，jlinkjlink相同的边相同的边EdgNode,*EdgLink;EdgNode,*EdgLink;typedef struct VexNode /typedef struct VexNode /顶点的结点结构顶点的结点结构VexTypeVexTypedata;data;/顶点数据顶点数据boolboolvisited;/visited;/顶点的访问标志，用于图的遍历顶点的访问标

40、志，用于图的遍历EdgLinkEdgLinkfirstedge;/firstedge;/指向第一条邻接边的指针指向第一条邻接边的指针VexNode,*VexLink;VexNode,*VexLink;typedef struct EdgListGraph /typedef struct EdgListGraph /图的结构图的结构VexNode *vex;/VexNode *vex;/顶点存储空间的基地址顶点存储空间的基地址int int vexnum;/vexnum;/顶点个数顶点个数int int vexsize;/vexsize;/顶点个数最大值顶点个数最大值int int arcnum

41、;/arcnum;/边的条数边的条数unsigned char unsigned char kind;kind;/图的种类图的种类 ALGraph;ALGraph;图的多重邻接表存储表示：34图的遍历，是是指指从从图图的的某某一一顶顶点点出出发发,访访问问图图中中的的所所有有的顶点的顶点,每个顶点仅被访问一次。每个顶点仅被访问一次。求解图的连通性求解图的连通性,拓朴排序及求关键路径等算法的基础。拓朴排序及求关键路径等算法的基础。但显然图的遍历要比树的遍历要复杂得多：但显然图的遍历要比树的遍历要复杂得多：(1)可从任一个顶点出发可从任一个顶点出发;而树只能从根出发而树只能从根出发(2)可可能能重

42、重复复访访问问某某顶顶点点,为为此此必必须须设设一一个个辅辅助助数数组组visitedn,用以判别顶点是否被访问。用以判别顶点是否被访问。一一般般有有两两条条遍遍历历图图的的路路径径：深深度度优优先先搜搜索索和和广广度度优优先先搜索。搜索。6.3 图的遍历图的遍历35类似树的先根遍历，是树的先根遍历的推广。类似树的先根遍历，是树的先根遍历的推广。假假设设连连通通图图的的某某个个顶顶点点v v的的所所有有邻邻接接点点为为：ww1 1、w w2 2、w wk k，从从顶顶点点v v出出发发的的深深度度优优先先遍遍历历算算法法的的递递归归描描述述如下：如下：1)1)访问顶点访问顶点v v；2)2)从

43、顶点从顶点v v的第的第1 1个邻接点个邻接点w w1 1出发进行深度优先访问；出发进行深度优先访问；3)3)从顶点从顶点v v的第的第2 2个邻接点个邻接点w w2 2出发进行深度优先访问；出发进行深度优先访问；4)4)依依此此类类推推，从从顶顶点点v v的的第第k k个个邻邻接接点点w wk k出出发发进进行行深深度度优先访问优先访问.由由于于每每个个结结点点要要求求都都要要访访问问到到，并并且且仅仅仅仅访访问问一一次次，因因此此在在顶顶点点的的存存储储结结构构中中需需要要增增加加一一个个访访问问标标志志域域visitedvisited，用用来来表表示示该该顶顶点点是是否否被被访访问问过过

44、。如如果果某某结结点点访问过时，应跳过。访问过时，应跳过。一、深度优先搜索36设设w w1 1、w w2 2和和w w3 3 均为均为v v的邻接点，的邻接点，SGSG1 1、SGSG2 2和和SGSG3 3分别分别为含顶点为含顶点w w1 1、w w2 2和和w w3 3的子图。的子图。从顶点从顶点v v出发的深度优先遍历如下：访问顶点出发的深度优先遍历如下：访问顶点v v，从，从顶点顶点v v的第的第1 1个邻接点个邻接点w w1 1出发进行深度优先访问，从顶出发进行深度优先访问，从顶点点v v的第的第2 2个邻接点个邻接点w w2 2出发进行深度优先访问，从顶点出发进行深度优先访问，从顶

45、点v v的第的第3 3个邻接点个邻接点w w3 3出发进行深度优先访问。出发进行深度优先访问。37n例如例如:由此得到顶点的访问序列为由此得到顶点的访问序列为:a ab be ed df fc c在进行遍历时，每个顶点访问并且仅仅访问一次。在进行遍历时，每个顶点访问并且仅仅访问一次。需要增加一个域需要增加一个域visitedvisited，用来表示该顶点是否被访，用来表示该顶点是否被访问过。在进行遍历之前，需要先把所有顶点的该标志域问过。在进行遍历之前，需要先把所有顶点的该标志域设置为设置为falsefalse。12345638Status DFS(ALGraph&G,VexType v)St

46、atus DFS(ALGraph&G,VexType v)/从顶点从顶点v v出发深度优先遍历连通图出发深度优先遍历连通图G,G,假定已经设定好遍历标志假定已经设定好遍历标志 int n=LocateVex(G,v);/int n=LocateVex(G,v);/查找顶点查找顶点v v。如果找不到。如果找不到,返回返回 if(n=-1)if(n=-1)return ERROR;return ERROR;if(G.vexn.visited)/if(G.vexn.visited)/如果已经访问过如果已经访问过,返回返回(递归的终止递归的终止)return ERROR;return ERROR;G.

47、vexn.visited=true;/G.vexn.visited=true;/访问该定点访问该定点 visit(G.vexn.data);/visit(G.vexn.data);/访问访问v v结点结点 p=G.vexn.firstarc;/p=G.vexn.firstarc;/深度优先访问该顶点的所有邻接点深度优先访问该顶点的所有邻接点 while(p)while(p)DFS(G,G.vexp-adjvex.data);DFS(G,G.vexp-adjvex.data);p=p-nextarc;p=p-nextarc;return OK;return OK;/DFSDFS深度优先收索算法:

48、39对于非连通图的遍历，刚可以对通过对图的各个连通分量依次对于非连通图的遍历，刚可以对通过对图的各个连通分量依次遍历，从而对整个图进行遍历。遍历，从而对整个图进行遍历。非连通图的深度优先遍历算法描述如下：非连通图的深度优先遍历算法描述如下：void DFSTraverse(ALGraph&G)void DFSTraverse(ALGraph&G)for(i=0;iG.vexnum;i+)for(i=0;iG.vexnum;i+)G.vexi.visited=false;G.vexi.visited=false;for(i=0;iG.vexnum;i+)for(i=0;iG.vexnum;i+)

49、if(!G.vexi.visited)if(!G.vexi.visited)DFS(G,G.vexi.data);DFS(G,G.vexi.data);/DFSTraverseDFSTraversen调用一次调用一次DFS()DFS()即可完成一个连通子图的遍历：即可完成一个连通子图的遍历：对于连通图来说，也就是说只需要调用一次对于连通图来说，也就是说只需要调用一次DFSDFS（），即可（），即可以完成整个图的遍历。以完成整个图的遍历。非连通图，可以用来求解图的连通分量。非连通图，可以用来求解图的连通分量。时间复杂度分析：时间复杂度分析：在在遍遍历历图图时时,对对图图中中每每个个顶顶点至多调用

50、一次点至多调用一次DFSDFS函数函数;遍遍历历图图的的过过程程实实质质上上是是对对每每个个顶顶点点查查找找其其邻邻接接点点的的过过程。程。其其耗耗时时主主要要取取决决于于所所采采用用的存储结构：的存储结构：当当用用二二维维数数组组表表示示邻邻接接矩矩阵阵作作图图的的存存储储结结构构时时,查查找找每每个个顶顶点点的的邻邻接接点点所所需需时时间间为为O O(n(n2 2),),其中其中n n为图中顶点数为图中顶点数;以以邻邻接接表表作作图图的的存存储储结结构构时时,找找邻邻接接点点的的时时间间为为O(e),O(e),其其中中e e为为无无向向图图中中边边的的数数或或有有向向图图中中弧弧的的数数。