专业课数据结构第7

1、机电工程学院机电工程学院程艺苑程艺苑数据结构数据结构教学内容教学内容 绪论绪论第第1 1章章 线性表线性表第第2 2章章 栈和队列栈和队列第第3 3章章 串串第第4 4章章 数组和广义表数组和广义表第第5 5章章 树和二叉树树和二叉树第第6 6章章 图图第第7 7章章 查找查找第第8 8章章 排序排序第第9 9章章第第7 7章章 图图u图图(Graph)(Graph)是一种比线性表和树更为复杂的数据结构。是一种比线性表和树更为复杂的数据结构。u线性结构：线性结构：是研究数据元素之间的是研究数据元素之间的一对一关系一对一关系。在这种。在这种结构中，除第一个和最后一个元素外，任何一个元素都有结构中

2、，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。唯一的一个直接前驱和直接后继。u树结构：树结构：是研究数据元素之间的是研究数据元素之间的一对多的关系一对多的关系。在这种。在这种结构中，每个元素对下结构中，每个元素对下( (层层) )可以有可以有0 0个或多个元素相联系，个或多个元素相联系，对上对上( (层层) )只有唯一的一个元素相关，数据元素之间有明显只有唯一的一个元素相关，数据元素之间有明显的层次关系。的层次关系。u图结构：图结构：是研究数据元素之间的是研究数据元素之间的多对多的关系多对多的关系。在这种。在这种结构中，任意两个元素之间可能存在关系。即结点之间的结构

3、中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。关系可以是任意的，图中任意元素之间都可能相关。u图的应用极为广泛，已渗入到诸如语言学、逻辑学、物图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。理、化学、电讯、计算机科学以及数学的其它分支。第第7 7章章 图图7 7.1 .1 图的基本概念图的基本概念7 7.2 .2 图的存储结构图的存储结构7 7.3 .3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径7.1

4、 7.1 图的基本概念图的基本概念7.1.1 7.1.1 图的定义和术语图的定义和术语定义：定义：图是由图是由顶点集合顶点集合(vertex)(vertex)及及顶点间的关系顶点间的关系集合组成集合组成的一种数据结构：的一种数据结构： GraphGraph( V, E ) ( V, E ) 其中其中: : V= V=x|xx|x 某个数据对象某个数据对象 是顶点的非空有穷集合；是顶点的非空有穷集合； E1=(x, y)| E1=(x, y)|x,yx,y V V 或或 E2=E2=|x,yx,y VVuE1E1是顶点间关系的有穷集合，也叫做是顶点间关系的有穷集合，也叫做边边(edge)(edg

5、e)集合，此时的图集合，此时的图称为称为无向图无向图(Digraph)(Digraph)。uE2E2表示从表示从x x到到y y的一条的一条弧弧(Arc)(Arc), ,且称且称x x为弧尾为弧尾,y,y为弧头，这样的图为弧头，这样的图称为称为有向图有向图( (UndigraphUndigraph) )。例例1：设有有向图：设有有向图G1和无向图和无向图G2，形式化定义分别是：，形式化定义分别是：G1=(V1 ，E1)V1=a,b,c,d,eE1=, , ,G2=(V2 ，E2)V2=a,b,c,dE2=(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)它们所对应

6、的图如下图所示。它们所对应的图如下图所示。abcd(b) (b) 无向图无向图G2 G2 (a) (a) 有向图有向图G1 G1 acbde我们用我们用n表示图中顶点数目，用表示图中顶点数目，用e表示边或弧的数目。下面的讨论中，表示边或弧的数目。下面的讨论中，不考虑顶点到其自身的弧或边，即若不考虑顶点到其自身的弧或边，即若 VR,则则 vi vj。u对于无向图，对于无向图，e的取值范围是的取值范围是0，n(n-1)/2 ，那么具有，那么具有n(n-1)/2条边的条边的无向图称为无向图称为完全无向图完全无向图，即图中任意两个不同的顶点间都有一条无向，即图中任意两个不同的顶点间都有一条无向边。边。

7、u对于有向图，对于有向图，e的取值范围是的取值范围是0，n(n-1) ，那么具有，那么具有n(n-1)条边的有向条边的有向图称为图称为完全有向图完全有向图，即图中任意两个不同的顶点间都有两条弧。，即图中任意两个不同的顶点间都有两条弧。u 有很少边或弧的图有很少边或弧的图(enn)的图称为的图称为稀疏图稀疏图(Sparse graph)，反之称，反之称为为稠密图稠密图(Dense graph)。u有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这些权可以

8、表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为这种带权的图通常称为网网(Network)。abcd(b) (b) 无向图无向图G2 G2 (a) (a) 有向图有向图G1 G1 acbdeu子图：子图：设有图设有图G=(VG=(V，E)E)和和G=(VG=(V，E)E)，若，若VV V V且且EE E E，则称图，则称图GG是是G G的的子图。子图。ABCD无向图无向图 G2AACDACABCD有向图有向图G1的子图的子图ABCDEABDEAABCDABCDE无向图无向图G2的子图的子图有向图有向图 G1u顶点的邻接顶点的邻接(Adjacent)(Adjacent)：对于无向图：

9、对于无向图G=(VG=(V，E)E)，若边，若边( (v,wv,w) ) E E，则称顶点，则称顶点v v和和w w互为互为邻接点邻接点，即，即v v和和w w相邻接。边相邻接。边( (v,wv,w) )依附依附(incident)(incident)与顶点与顶点v v和和w w 。u对于有向图对于有向图G=(VG=(V，E)E)，若有向弧，若有向弧 E E，则称顶点，则称顶点v v“邻接到邻接到”顶点顶点w w，顶点，顶点w w“邻接自邻接自”顶点顶点v v，弧，弧 与顶与顶点点v v和和w w“相关联相关联”。u顶点的度、入度、出度：顶点的度、入度、出度：以顶点以顶点v v为头的弧的数目称

10、为为头的弧的数目称为v v的的入度入度( (I InDnDegreeegree) )，记为，记为I ID(v);D(v);以以v v为尾的弧的数目称为为尾的弧的数目称为v v的的出 度出 度 ( ( O u t D e g r e eO u t D e g r e e ) ) ， 记 为， 记 为 O D ( v ) ;O D ( v ) ; 顶 点顶 点 v v 的 度 为的 度 为TD(v)=ID(v)+OD(v)TD(v)=ID(v)+OD(v)。 V0 V1 V2 V3u一般地，如果顶点一般地，如果顶点v vi i的度记为的度记为TD(v),TD(v),那么一那么一个有个有n n个顶点

11、，个顶点，e e条边或弧的图满足如下关系：条边或弧的图满足如下关系：11()2niieTD v路径、回路路径、回路( (环环) )u无向图无向图G G1 1= =（V V1 1，E E1 1）中从顶点）中从顶点v v到顶点到顶点vv的路径的路径(Path)(Path)是一个顶点序列是一个顶点序列(v=v(v=vi 0i 0，v vi 1i 1，,v,vi mi m=v),=v),其中其中(v(vi i,v,vi+1i+1) ) E E1 1 ( ( i i=1,2,k-1)=1,2,k-1)。第一个顶点和最后一个顶。第一个顶点和最后一个顶点相同的路径称为回路或环。点相同的路径称为回路或环。在在

12、G G1 1中，中，v v0 0,v,v1 1,v,v2 2,v,v3 3 是是v v0 0到到v v3 3的路径；的路径； v v0 0,v,v1 1,v,v2 2,v,v3 3 , , v v0 0是回路。是回路。u 如果是有向图如果是有向图G G2 2= =（V V2 2，E E2 2），则路径也是有向的。），则路径也是有向的。在在G G2 2中，中，v v0 0, v, v2 2, v, v3 3是是v v0 0到到v v3 3的路径；的路径； v v0 0,v,v2 2,v,v3 3,v,v0 0是回路。是回路。无向图无向图G1有向图有向图G2 V0 V4 V3 V1 V2 V0 V

13、1 V2 V3u序列中顶点不重复出现的路径称序列中顶点不重复出现的路径称为为简单路径简单路径。除了第一个顶点和最。除了第一个顶点和最后一个顶点之外，其余顶点不重复后一个顶点之外，其余顶点不重复出现的回路，称出现的回路，称简单回路或环简单回路或环。连通、连通分量和连通图、生成树连通、连通分量和连通图、生成树在无向图在无向图G G中：中：u如果从顶点如果从顶点V Vi i 到顶点到顶点V Vj j有路径，则称有路径，则称V Vi i与与V Vj j是是连通的连通的。u如果图中任意两个顶点都连通，则称如果图中任意两个顶点都连通，则称G G为为连通图连通图，否则称，否则称为为非连通图非连通图。u在非连

14、通图在非连通图G G中，任何一个极大连通子图称为中，任何一个极大连通子图称为G G的的连通分量连通分量。u任何连通图的连通分量只有一个，即其自身，而非连通图任何连通图的连通分量只有一个，即其自身，而非连通图有多个连通分量。有多个连通分量。u在一个连通图中，含有全部顶点的极小在一个连通图中，含有全部顶点的极小( (边数最少边数最少) )连通子连通子图，称为该连通图的图，称为该连通图的生成树生成树。( (包含图的所有包含图的所有 n n 个结点，个结点，但只含图的但只含图的 n-1 n-1 条边。在生成树中添加一条边之后，必定条边。在生成树中添加一条边之后，必定会形成回路或环会形成回路或环) )非

15、连通图非连通图G4G4A AB BC CD DE EF FG GI IJ JK KA AB BC CD DE EI IJ JK KF FG G非连通图非连通图G4G4的三个连通分量的三个连通分量连通图连通图G5G5A AB BC CD D连通图连通图G5G5的两棵生成树的两棵生成树A AB BC CD DA AB BC CD D强连通、强连通分量和强连通图强连通、强连通分量和强连通图在有向图在有向图G G中：中：u存在从顶点存在从顶点V Vi i 到顶点到顶点V Vj j的路径，也存在从顶点的路径，也存在从顶点V Vj j 到顶点到顶点V Vi i的路径，则称的路径，则称V Vi i与与V V

16、j j是是强连通强连通的。的。u如果图中任意两个顶点都是强连通，则称如果图中任意两个顶点都是强连通，则称G G为为强连通图强连通图，否则称为否则称为非强连通图非强连通图。u在非强连通图在非强连通图G G中，任何一个极大强连通子图称为中，任何一个极大强连通子图称为G G的的强强连通分量连通分量。u任何强连通图的强连通分量只有一个，即其自身，而非任何强连通图的强连通分量只有一个，即其自身，而非强连通图有多个强连通分量。强连通图有多个强连通分量。有向图有向图G G和强连通分量示例：和强连通分量示例：A AB BC CD DE EF FA AB BC CD DE EF F(a)有向图有向图G(c)强连

17、通分量强连通分量2(b)强连通分量强连通分量1(d)强连通分量强连通分量37.1.2 7.1.2 图的抽象数据类型定义图的抽象数据类型定义ADT Graph数据对象数据对象V：具有相同特性的数据元素的集合，称为顶：具有相同特性的数据元素的集合，称为顶点集点集。数据关系数据关系R：R=VRVR=| v,w Vp(v,w) ，表示表示 从从v到到w的弧，的弧，P(v,w)定义了弧定义了弧的信息的信息 基本操作基本操作P： ADT Graph 基本操作基本操作P:结构的建立和销毁结构的建立和销毁: :CreateGraphCreateGraph(&G,V,VR); / (&G,V,V

18、R); / 按按V V和和VRVR的定义构造图的定义构造图G G。DestroyGraphDestroyGraph(&G); / (&G); / 销毁图销毁图G G。对顶点的访问操作对顶点的访问操作: :LocateVexLocateVex(G, u); / (G, u); / 若若G G中存在顶点中存在顶点u u，则返回该顶点在，则返回该顶点在图中位置；否则返回其它信息。图中位置；否则返回其它信息。GetVexGetVex(G, v); / (G, v); / 返回返回v v的值。的值。PutVexPutVex(&G, v, value); / (&G, v,

19、 value); / 对对v v赋值赋值valuevalue。对邻接点的操作对邻接点的操作: :FirstAdjVexFirstAdjVex(G, v); / (G, v); / 返回返回v v的第一个邻接点。若该顶点的第一个邻接点。若该顶点/在在G G中没有邻接点，则返回中没有邻接点，则返回“空空”。NextAdjVexNextAdjVex(G, v, w); /(G, v, w); /返回返回v v的（相对于的（相对于w w的）下一个的）下一个 邻接点。若邻接点。若w w是是v v的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。 插入或删除顶点插入或删除顶点InsertVexIn

20、sertVex(&G, v); / (&G, v); / 在图在图G G中增添新顶点中增添新顶点v v。DeleteVexDeleteVex(&G, v); / (&G, v); / 删除删除G G中顶点中顶点v v及其相关的弧。及其相关的弧。插入和删除弧插入和删除弧InsertArcInsertArc(&G, v, w); / (&G, v, w); / 在在G G中增添弧中增添弧 ，若，若G G是无是无向的，则还增添对称弧向的，则还增添对称弧 。DeleteArcDeleteArc(&G, v, w); /(&G, v, w)

21、; /在在G G中删除弧中删除弧 ，若，若G G是无是无 向的，则还删除对称弧向的，则还删除对称弧 。遍历遍历DFSTraverseDFSTraverse(G, v, Visit(); / (G, v, Visit(); / 从顶点从顶点v v起深度优先遍起深度优先遍历图历图G G，并对每个顶点调用函数，并对每个顶点调用函数VisitVisit一次且仅一次。一次且仅一次。BFSTraverseBFSTraverse(G, v, Visit(); / (G, v, Visit(); / 从顶点从顶点v v起广度优先遍起广度优先遍历图历图G G，并对每个顶点调用函数，并对每个顶点调用函数Visit

22、Visit一次且仅一次。一次且仅一次。7.2 7.2 图的存储结构图的存储结构 图的存储结构比较复杂，其图的存储结构比较复杂，其复杂性复杂性主要表现在：主要表现在：u任意顶点之间可能存在联系，无法以数据元素在任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。存储区中的物理位置来表示元素之间的关系。u图中顶点的度不一样，有的可能相差很大，若按图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，元，反之按每个顶点自己的度设计不同的结构，又会影响操作。又

23、会影响操作。 图的存储结构至少要保存两类信息：图的存储结构至少要保存两类信息： (1)顶点的数据；顶点的数据； (2)顶点间的关系。顶点间的关系。 如何表示顶点间的关系？如何表示顶点间的关系？ V0 V4 V3 V1 V2 V0 V1 V2 V3常用图的存储表示常用图的存储表示图的数组图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示图的邻接表存储表示图的邻接表存储表示有向图的十字链表存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示无向图的邻接多重表存储表示 7.2.1 7.2.1 邻接矩阵邻接矩阵( (数组数组) )表示法表示法 基本思想：基本思想：对于有对于有n n个顶点的图，

24、用个顶点的图，用一维数组一维数组vexsvexsnn存储顶点信息存储顶点信息，用，用二维数组二维数组AnnAnn存储存储顶点之间关系的信息顶点之间关系的信息。该二维数组称为邻接矩阵。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在在邻接矩阵中，以顶点在vexsvexs数组中的下标代表数组中的下标代表顶点，邻接矩阵中的顶点，邻接矩阵中的元素元素AAi ijj存放的是顶点存放的是顶点i i到顶点到顶点j j之间关系的信息之间关系的信息。1 无向图的数组表示无向图的数组表示(1) (1) 无权图的邻接矩阵无权图的邻接矩阵 无向无权图无向无权图G=(V，E)有有n(n1)个顶点，其邻接矩阵是个顶点，其邻

25、接矩阵是n阶对称方阵，如图下图所示。其元素的定义如下：阶对称方阵，如图下图所示。其元素的定义如下：1 若若(vi , vj) E，即，即vi , vj邻接邻接0 若若(vi , vj) E，即，即vi , vj不邻接不邻接Aij=(a) 无向图无向图 abcd无向无权图的数组存储无向无权图的数组存储(b) 顶点矩阵顶点矩阵vexsabcd0 1 1 11 0 1 11 1 0 11 1 1 0(c) 邻接矩阵邻接矩阵(2) 带权图的邻接矩阵带权图的邻接矩阵 无向带权图无向带权图G=(VG=(V，E) E) 的邻接矩阵如下图所示。其元素的邻接矩阵如下图所示。其元素的定义如下：的定义如下：(a)

26、带权无向图带权无向图 (b) 顶点矩阵顶点矩阵无向带权图的数组存储无向带权图的数组存储(c) 邻接矩阵邻接矩阵354126abcde3vexsabcde 6 2 6 3 4 32 3 1 4 3 5 3 5 Wij 若若(vi , vj) E，即，即vi , vj邻接，权值为邻接，权值为wij 若若(vi , vj) E，即，即vi , vj不邻接时不邻接时Aij=(3) (3) 无向图邻接矩阵的特性无向图邻接矩阵的特性 邻接矩阵是邻接矩阵是对称方阵对称方阵； 对于顶点对于顶点vi，其度数是第，其度数是第i行的非行的非0元素的个数；元素的个数； 无向图的边数是上无向图的边数是上(或下或下)三角

27、形矩阵中非三角形矩阵中非0元素个数。元素个数。0 1 1 11 0 1 11 1 0 11 1 1 0 6 2 6 3 4 32 3 1 4 3 5 3 5 2 2 有向图的数组表示有向图的数组表示(1) (1) 无权图的邻接矩阵无权图的邻接矩阵 若有向无权图若有向无权图G=(VG=(V，E)E)有有n(n1)n(n1)个顶点，则其邻接矩个顶点，则其邻接矩阵是阵是n n阶方阵，如下图所示。元素定义如下：阶方阵，如下图所示。元素定义如下：1 若若 E，从，从vi到到vj有弧有弧Aij=0 若若 E 从从vi到到vj 没有弧没有弧(a) 有向图有向图acbde 有向无权图的数组存储有向无权图的数组

28、存储(b) 顶点矩阵顶点矩阵vexsabcde(c) 邻接矩阵邻接矩阵0 0 1 1 0 10 10 0 0 0 00 0 0 1 1 11 1 1 0 0 00 0 0 0 0 1 0(2) (2) 带权图的邻接矩阵带权图的邻接矩阵 有向带权图有向带权图G=(VG=(V，E)E)的邻接矩阵如下图所示。其元素的的邻接矩阵如下图所示。其元素的定义如下：定义如下：wij 若若 E，即，即vi , vj邻接，权值为邻接，权值为wij 若若 E，即，即vi , vj不邻接时不邻接时Aij= 带权有向图的数组存储带权有向图的数组存储(b) 顶点矩阵顶点矩阵vexsabcde(c) 邻接矩阵邻接矩阵 6

29、2 3 3 1 4 4 5 (a) 带权有向图带权有向图 354126abcde3 有向图邻接矩阵的特性有向图邻接矩阵的特性 对于顶点对于顶点v vi i，第，第i i行的非行的非0 0元素的个数是其出度元素的个数是其出度OD(vOD(vi i) )；第第i i列的非列的非0 0元素的个数是其入度元素的个数是其入度ID(vID(vi i) ) 。 邻接矩阵中非邻接矩阵中非0 0元素的个数就是图的弧的数目。元素的个数就是图的弧的数目。0 0 1 1 0 10 10 0 0 0 00 0 0 1 1 11 1 1 0 0 00 0 0 0 0 1 0 6 2 3 3 1 4 4 5 7.2.2 7

30、.2.2 邻接链表法邻接链表法 基本思想：基本思想：对图的每个顶点建立一个对图的每个顶点建立一个单链表单链表，存储该存储该顶点所有邻接顶点及其相关信息顶点所有邻接顶点及其相关信息。每一个。每一个单链表设一个单链表设一个表头结点表头结点。 第第i个单链表中的结点表示依附于顶点个单链表中的结点表示依附于顶点Vi的边的边(对有向图是以顶点对有向图是以顶点Vi为尾的弧为尾的弧)。1 1 结点结构与邻接链表示例结点结构与邻接链表示例 链表中的结点称为链表中的结点称为表结点表结点，每个结点由三个域组成，如，每个结点由三个域组成，如下图所示。下图所示。邻接点域邻接点域(adjvex)指示与顶点指示与顶点Vi

31、邻接的顶点在图中的位置邻接的顶点在图中的位置(顶点编号顶点编号)；链域链域(nextarc)指向下一个与顶点指向下一个与顶点Vi邻接的表结点；邻接的表结点；数据域数据域(info)存储和边或弧相关的信息，如权值等。存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。对于无权图，如果没有与边相关的其他信息，可省略此域。 每个链表设一个每个链表设一个表头结点表头结点(称为顶点结点称为顶点结点)，由两个域组，由两个域组成，如图所示。成，如图所示。链域链域(firstarc)指向链表中的第一个结点；指向链表中的第一个结点；数据域数据域(data) 存储顶点名或其他信息

32、。存储顶点名或其他信息。adjvex info nextarc表结点表结点：data firstarc顶点结点顶点结点： 邻接链表结点结构邻接链表结点结构 在图的邻接链表表示中，在图的邻接链表表示中，所有顶点结点所有顶点结点用一用一个向量以顺序结构形式存储，可以随机访问任意个向量以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为顶点的链表，该向量称为表头向量表头向量，向量的下标，向量的下标指示顶点的序号。指示顶点的序号。无向图及其邻接链表无向图及其邻接链表v1v2v3v4v501234MAX_VEX-1v1 v2v3 v4 v5 213 02 0314 204 23 (a) 有向图有向

33、图v1v2v3v4v513 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 (b) 正邻接链表，出度直观正邻接链表，出度直观2 02 2 01234MAX_VEX-1v1 1v2 2v3 1v4 2 v5 1 3 04 (c) 逆邻接链表，入度直观逆邻接链表，入度直观有向图及其邻接链表有向图及其邻接链表对有向图，其邻接链表对有向图，其邻接链表有两种形式，如图所示。有两种形式，如图所示。2 2 邻接表法的特点邻接表法的特点表头向量中每个分量就是一个单链表的头结点，分量个表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；数就是图中的顶

34、点数目；在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；示节省存储空间；在在无向图无向图，顶点，顶点V Vi i的度是第的度是第i i个链表的结点数；个链表的结点数；对对有向图有向图可以建立可以建立正邻接表或逆邻接表正邻接表或逆邻接表。正邻接表是以。正邻接表是以顶点顶点V Vi i为出度为出度( (即为弧的起点即为弧的起点) )而建立的邻接表；逆邻接表而建立的邻接表；逆邻接表是以顶点是以顶点V Vi i为入度为入度( (即为弧的终点即为弧的终点) )而建立的邻接表；而建立的邻接表；在在有向图有向图中，第中，第i i个链表中的结点数

35、是顶点个链表中的结点数是顶点V Vi i的出的出 ( (或入或入) )度；求入度；求入 ( (或出或出) )度，须遍历整个邻接表；度，须遍历整个邻接表；在邻接表上容易找出任一顶点的第一个邻接点和下一个在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点。邻接点。7.2.3 7.2.3 十字链表法十字链表法 十字链表十字链表(Orthogonal List)(Orthogonal List)是有向图的另一种链式存是有向图的另一种链式存储结构，是将有向图的储结构，是将有向图的正邻接表和逆邻接表结合正邻接表和逆邻接表结合起来得到的起来得到的一种链表。一种链表。 在这种结构中，每条弧的弧头结点和弧尾

36、结点都存放在在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到链表中，并将弧结点分别组织到以弧尾结点为头以弧尾结点为头( (顶点顶点) )结点结点和以弧头结点为头和以弧头结点为头( (顶点顶点) )结点结点的链表中。这种结构的结点逻的链表中。这种结构的结点逻辑结构如下图所示。辑结构如下图所示。弧结点弧结点tailvex headvex info hlink tlink顶点结点顶点结点Data firstin firstout十字链表结点结构十字链表结点结构 datadata域：域：存储和顶点相关的信息；存储和顶点相关的信息； 指针域指针域firstinfirstin：

37、指向以该顶点为弧头的第一条弧所对指向以该顶点为弧头的第一条弧所对应的弧结点；应的弧结点； 指针域指针域firstoutfirstout：指向以该顶点为弧尾的第一条弧所对指向以该顶点为弧尾的第一条弧所对应的弧结点；应的弧结点； 尾域尾域tailvextailvex：指示弧尾顶点在图中的位置；指示弧尾顶点在图中的位置； 头域头域headvexheadvex：指示弧头顶点在图中的位置；指示弧头顶点在图中的位置； 指针域指针域hlinkhlink：指向弧头相同的下一条弧；指向弧头相同的下一条弧； 指针域指针域tlinktlink：指向弧尾相同的下一条弧；指向弧尾相同的下一条弧； InfoInfo域：域

38、：指向该弧的相关信息。指向该弧的相关信息。弧结点弧结点tailvex headvex info hlink tlink顶点结点顶点结点Data firstin firstout十字链表结点结构十字链表结点结构 下图所示是一个有向图及其十字链表下图所示是一个有向图及其十字链表( (略去了表结点的略去了表结点的infoinfo域域) )。从这种存储结构图可以看出，从一个顶点结点的。从这种存储结构图可以看出，从一个顶点结点的firstoutfirstout出发，沿表结点的出发，沿表结点的tlinktlink指针构成了正邻接表的链指针构成了正邻接表的链表结构，而从一个顶点结点的表结构，而从一个顶点结点

39、的firstinfirstin出发，沿表结点的出发，沿表结点的hlinkhlink指针构成了逆邻接表的链表结构。指针构成了逆邻接表的链表结构。V V0 0V V1 1V V2 2V V3 30 10 2 2 02 3 3 0 3 1 3 2 0213V0V1 V2V3有向图的十字链表结构有向图的十字链表结构7.2.4 7.2.4 邻接多重表邻接多重表 邻接多重表邻接多重表(Adjacency (Adjacency MultilistMultilist) )是无向图的另一种是无向图的另一种链式存储结构。这是一种有效的存储结构，在无向图的邻链式存储结构。这是一种有效的存储结构，在无向图的邻接表中，

40、接表中，一条边一条边( (v,wv,w) )的两个表结点分别出现在以的两个表结点分别出现在以v v和和w w为头为头结点的链表结点的链表中，很容易求得顶点和边的信息，但在涉及到中，很容易求得顶点和边的信息，但在涉及到边的操作会带来不便。边的操作会带来不便。 邻接多重表的结构和十字链表类似，每条边用一个结邻接多重表的结构和十字链表类似，每条边用一个结点表示；邻接多重表中的顶点结点结构与邻接表中的完全点表示；邻接多重表中的顶点结点结构与邻接表中的完全相同，而表结点包括六个域，如图所示。相同，而表结点包括六个域，如图所示。data firstedge顶点结点顶点结点 邻接多重表的结点结构邻接多重表的

41、结点结构表结点表结点mark ivex jvex info ilink jlink DataData域：域：存储和顶点相关的信息；存储和顶点相关的信息； 指针域指针域firstedgefirstedge：指向依附于该顶点的第一条边所对指向依附于该顶点的第一条边所对应的表结点；应的表结点； 标志域标志域markmark：用以标识该条边是否被访问过；用以标识该条边是否被访问过； ivexivex和和jvexjvex域：域：分别保存该边所依附的两个顶点在图分别保存该边所依附的两个顶点在图中的位置；中的位置； infoinfo域：域：保存该边的相关信息；保存该边的相关信息； 指针域指针域ilinkil

42、ink：指向下一条依附于顶点指向下一条依附于顶点ivexivex的边；的边； 指针域指针域jlinkjlink：指向下一条依附于顶点指向下一条依附于顶点jvexjvex的边；的边；data firstedge顶点结点顶点结点 邻接多重表的结点结构邻接多重表的结点结构表结点表结点mark ivex ilink jvex info jlink邻接多重表与邻接表的区别：邻接多重表与邻接表的区别： 后者的同一条边用两个表结点表示，而前者后者的同一条边用两个表结点表示，而前者只用一个表结点表示只用一个表结点表示；除标志域外，邻接多重表除标志域外，邻接多重表与邻接表表达的信息是相同的，因此，操作的实与邻接

43、表表达的信息是相同的，因此，操作的实现也基本相似。现也基本相似。无向图及其多重邻接链表无向图及其多重邻接链表v1v2v3v4v1v2v3v40123 0 1 0 2 2 1 2 3 0 37.3 7.3 图的遍历图的遍历 图的遍历图的遍历( (TraveringTravering Graph) Graph)：从图的某一顶点出发，从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是各种图的其他操作的基础。历算法是各种图的其他操作的基础。 复杂性：复杂性：图的任意顶点可能和其余的顶点相邻接，图的任意顶点可能和其余的顶点相邻

44、接，可能在访问了某个顶点后，沿某条路径搜索后又回到原可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。顶点。 解决办法：解决办法：在遍历过程中记下已被访问过的顶点。在遍历过程中记下已被访问过的顶点。设置一个辅助向量设置一个辅助向量Visited0Visited0n-1(nn-1(n为顶点数为顶点数) )，其初，其初值为值为0 0，一旦访问了顶点，一旦访问了顶点v vi i后，使后，使VisitedVisitedi i 为为1 1或为访或为访问的次序号。问的次序号。 图的遍历算法有图的遍历算法有深度优先搜索算法深度优先搜索算法和和广度优先搜索算法广度优先搜索算法。7.3.1 7.3.1 深度

45、优先搜索算法深度优先搜索算法 深度优先搜索深度优先搜索(Depth First Search-DFS)(Depth First Search-DFS)遍历类似树遍历类似树的先序遍历，是树的先序遍历的推广。的先序遍历，是树的先序遍历的推广。1 1 算法思想算法思想 设初始状态时图中的所有顶点未被访问，深度优先搜索设初始状态时图中的所有顶点未被访问，深度优先搜索从图中某个初始顶点从图中某个初始顶点v v出发出发, ,首先访问初始顶点首先访问初始顶点v,v,然后选择然后选择一个与顶点一个与顶点v v相邻且没被访问过的顶点相邻且没被访问过的顶点w w为初始顶点为初始顶点, ,再从再从w w出发进行深度

46、优先搜索出发进行深度优先搜索, ,直到图中与当前顶点直到图中与当前顶点v v邻接的所有邻接的所有顶点都被访问过为止。显然顶点都被访问过为止。显然, ,这个遍历过程是个递归过程。这个遍历过程是个递归过程。 无向图深度优先搜索遍历无向图深度优先搜索遍历(a) 无向图无向图Gv1v2v3v4v5(b) G的邻接链表的邻接链表01234MAX_VEX-1v1 v2v3 v4 v5 21 20 01 4 3 下图是无向图的深度优先搜索遍历示例下图是无向图的深度优先搜索遍历示例( (红色箭头红色箭头) )。某一种某一种DFSDFS次序是：次序是：v v1 1 v v3 3 v v2 2 v v4 4 v

47、v5 5例：例：求图求图G G以以V V0 0起始点的的深度优先序列。起始点的的深度优先序列。 V0 V7 V6 V5 V4 V3 V2 V1,V6V0V1V3V2V7V5 V4V0 ,V1 ,V4 ,V7 ,V3 ,V2 ,V5 ,V6 V0 ,V1,V3,V7,V4,V2,V5图图GV6由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，DFS序列不是唯一的序列不是唯一的DFSDFS遍历类似遍历类似树的先序遍历树的先序遍历如果将图的顶点的未被访问邻接点看作树结点的孩子，如果将图的顶点的未被访问邻接点看作树结点的孩子，图的深度优先遍历与树的先根遍历是图的深度优先遍历与树的先根遍历是类

48、似类似的。的。 图的深度优先遍历图的深度优先遍历 从图中某顶点从图中某顶点v v出发：出发： （1 1）访问顶点）访问顶点v v； （2 2）依次从）依次从v v的未被访问的邻接点的未被访问的邻接点 出发，对图进行深度优先遍历。出发，对图进行深度优先遍历。树的先根遍历树的先根遍历 若树非空若树非空 （1 1）访问根结点；）访问根结点； （2 2）依次先根遍历各棵子树。）依次先根遍历各棵子树。比较比较2 2 算法实现算法实现 由算法思想知，这是一个递归过程。由算法思想知，这是一个递归过程。在遍历过程中便于在遍历过程中便于区分顶点是否已被访问，设置访问标志数区分顶点是否已被访问，设置访问标志数Vi

49、sited0Visited0n-1 n-1 (n(n为顶点数为顶点数) )，其初值为，其初值为0 0，一旦访问了顶点，一旦访问了顶点v vi i后，使后，使VisitedVisitedi i 为为1 1。void DFS(Graph G, int v) /算法7.4 /从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v);w=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); /对v的尚未访问的邻接顶点w，递归调用DFS /DFSF F F F F F

50、 F F F0 1 2 3 4 5 6 7 8T T T T T T T T Tach dfke bg访问标志访问标志: :访问次序访问次序: :例如例如: :abchdekfg812345670achkfedbg3 3 算法分析算法分析遍历时，对图的每个顶点至多调用一次遍历时，对图的每个顶点至多调用一次DFSDFS函数，因为一旦某个顶点被标志成为已被访问，函数，因为一旦某个顶点被标志成为已被访问，就不再从它出发进行搜索。遍历图的过程实质上就不再从它出发进行搜索。遍历图的过程实质上就是就是对每个顶点查找邻接顶点的过程对每个顶点查找邻接顶点的过程，其耗费的，其耗费的时间取决于所采用的存储结构。时

51、间取决于所采用的存储结构。当用二维数组表示邻接矩阵作为图的存储结当用二维数组表示邻接矩阵作为图的存储结构时，查找每个顶点的邻接点所需时间为构时，查找每个顶点的邻接点所需时间为O(nO(n2 2) .) .当以邻接表作图的存储结构时，找邻接点所当以邻接表作图的存储结构时，找邻接点所需时间为需时间为O(e)O(e)，e e为无向图中边的数或有向图中弧为无向图中边的数或有向图中弧的数，此时的时间复杂度为的数，此时的时间复杂度为O(O(n+en+e) ) 。7.3.2 7.3.2 广度优先搜索算法广度优先搜索算法 广度优先搜索广度优先搜索(Breadth First Search-BFS)(Bread

52、th First Search-BFS)遍历类遍历类似树的按层次遍历的过程。似树的按层次遍历的过程。1 1 算法思想算法思想 广度优先搜索遍历的过程是：首先访问初始点广度优先搜索遍历的过程是：首先访问初始点v vi i, ,接着接着访问访问v vi i的所有未被访问过的邻接点的所有未被访问过的邻接点v vi1i1,v,vi2i2,v vitit, ,然后再按然后再按照照v vi1i1,v,vi2i2,v vitit的次序的次序, ,访问每一个顶点的所有未被访问过访问每一个顶点的所有未被访问过的邻接点的邻接点, ,依次类推依次类推, ,直到图中所有和初始点直到图中所有和初始点v vi i有路径相

53、通有路径相通的顶点都被访问过为止。的顶点都被访问过为止。下图是有向图的广度优先搜索遍历示例下图是有向图的广度优先搜索遍历示例(红色箭头红色箭头)。上述图的上述图的BFS次序是次序是：v1 v2 v4 v3 v5(b) G的正邻接链表的正邻接链表13 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 有向图广度优先搜索遍历有向图广度优先搜索遍历(a) 有向图有向图Gv1v2v3v4v5例：例：求图求图G G以以V V0 0起始点的的广度优先序列。起始点的的广度优先序列。 V0 V7 V6 V5 V4 V3 V2 V1,V7V0V1V3V2V7V5 V4V

54、0 ,V2 ,V1 ,V5 ,V6 ,V3 ,V4 ,V7 V0 ,V1,V2,V3,V4,V5,V6图图GV6由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，BFS序列不是唯一的序列不是唯一的BFSBFS遍历类似遍历类似树的按层次遍历树的按层次遍历2 2 算法实现算法实现 为了标记图中顶点是否被访问过，同样需要一个访问为了标记图中顶点是否被访问过，同样需要一个访问标记数组；其次，为了依次访问与标记数组；其次，为了依次访问与v vi i相邻接的各个顶点，相邻接的各个顶点，需要附加一个队列来保存访问需要附加一个队列来保存访问v vi i的相邻接的顶点。的相邻接的顶点。typedef

55、emnu FALSE , TRUE BOOLEAN ;BOOLEAN VisitedMAX_VEX ;typedef struct Queue int elemMAX_VEX ;int front , rear ;Queue ; /* 定义一个队列保存将要访问顶点 */void BFSTraverse(Graph G, Status (*Visit)(int v) /算法算法7.6 for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; v=0 ; w=NextAdjVex(

56、G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); /if /while /if / BFSTraverse 用广度优先搜索算法遍历图与深度优先搜索用广度优先搜索算法遍历图与深度优先搜索算法遍历图的算法遍历图的唯一区别是邻接点搜索次序不同唯一区别是邻接点搜索次序不同，因此，当以邻接表作图的存储结构时广度优先搜因此，当以邻接表作图的存储结构时广度优先搜索算法遍历图的总时间复杂度也为索算法遍历图的总时间复杂度也为O(O(n+en+e) )。 图的遍历可以系统地访问图中的每个顶点，图的遍历可以系统地访问图中的每个顶点，因此，

57、图的遍历算法是图的最基本、最重要的算因此，图的遍历算法是图的最基本、最重要的算法，许多有关图的操作都是在图的遍历基础之上法，许多有关图的操作都是在图的遍历基础之上加以变化来实现的。加以变化来实现的。7.4 7.4 图的连通性问题图的连通性问题7.4.1 7.4.1 无向图的连通分量与生成树无向图的连通分量与生成树 对于无向图，对其进行遍历时：对于无向图，对其进行遍历时： 若是若是连通图连通图：仅需从图中仅需从图中任一顶点出发任一顶点出发，就，就能访问图中的所有顶点；能访问图中的所有顶点； 若是若是非连通图非连通图：需从图中需从图中多个顶点出发多个顶点出发。每。每次从一个新顶点出发所访问的顶点集

58、序列次从一个新顶点出发所访问的顶点集序列恰好恰好是是各个连通分量的顶点集。各个连通分量的顶点集。(a) 无向图无向图Gv1v2v3v4v5(b) G的邻接链表的邻接链表01234MAX_VEX-1v1 v2v3 v4 v5 21 20 01 4 3 无向图及深度优先生成森林无向图及深度优先生成森林(c) 深度优先生成森林深度优先生成森林v1v2v3v4v5 如图所示的无向图是非连通图，按图中给定的邻如图所示的无向图是非连通图，按图中给定的邻接表进行深度优先搜索遍历，接表进行深度优先搜索遍历，2 2次调用次调用DFSDFS所得到的顶点所得到的顶点访问序列集是：访问序列集是： v1 ,v3 ,v2

59、 v1 ,v3 ,v2和和 v4 ,v5 v4 ,v5 若若G=(V,E)G=(V,E)是是无向连通图无向连通图， 顶点集和边集分别是顶点集和边集分别是V(G) V(G) ，E(G) E(G) 。若从。若从G G中任意点出发遍历时，中任意点出发遍历时， E(G)E(G)被被分成两个互不相交的集合：分成两个互不相交的集合：T(G) T(G) ：遍历过程中：遍历过程中所经过的边所经过的边的集合；的集合；B(G) B(G) ：遍历过程中：遍历过程中未经过的边未经过的边的集合；的集合； 显然：显然： E(G)=T(G)B(G) E(G)=T(G)B(G) ，T(G)B(G)=T(G)B(G)= 显然，

60、图显然，图G=(V, T(G)G=(V, T(G)是是G G的的极小连通子图极小连通子图，且，且GG是一棵树。是一棵树。GG称为图称为图G G的一棵的一棵生成树生成树。 从任意点出发按从任意点出发按DFSDFS算法得到生成树算法得到生成树GG称为称为深度深度优先生成树优先生成树；按；按BFSBFS算法得到的算法得到的GG称为称为广度优先生成广度优先生成树树。深度优先遍历序列：深度优先遍历序列：1,2,4,8,6,3,7,5广度优先遍历序列：广度优先遍历序列：1,2,3,4,5,6,7,8若若G=(V,E)G=(V,E)是是无向非连通图无向非连通图，对图进行遍历时得到，对图进行遍历时得到若干个连通分量的顶点集：若干个连通分量的顶点集：V V1 1(G) ,V(G) ,V2 2(G) ,(G) ,