数据结构第7章

1、计算机科学与技术学院计算机科学与技术学院曲立平曲立平Email： Data StructureData StructurePage 22022-3-2q 学习目标学习目标v领会领会图的类型定义图的类型定义。v熟悉熟悉图的各种存储结构图的各种存储结构及其及其构造构造算法，了解各种存储结构的特点算法，了解各种存储结构的特点及其及其选用原则选用原则。v熟练掌握图的两种熟练掌握图的两种遍历遍历算法。算法。v理解各种图的理解各种图的应用问题的算法应用问题的算法。q 重点和难点重点和难点v重点：图的各种应用问题的算法都比较经典，注意重点：图的各种应用问题的算法都比较经典，注意理解各种图的理解各种图的算法及

2、其应用场合算法及其应用场合。Data StructureData StructurePage 32022-3-2q 知识点知识点v图的类型定义图的类型定义v图的存储表示图的存储表示v图的深度优先搜索遍历和广度优先搜索遍历图的深度优先搜索遍历和广度优先搜索遍历v无向网的最小生成树无向网的最小生成树v拓扑排序拓扑排序v关键路径关键路径v最短路径最短路径Data StructureData StructurePage 42022-3-2q线性表线性表v每个数据元素只有一个直接前驱和一个直接后继。每个数据元素只有一个直接前驱和一个直接后继。q树形结构树形结构v每个数据元素只有一个直接前驱，但可能有多个

3、直接后继。每个数据元素只有一个直接前驱，但可能有多个直接后继。q图形结构图形结构v每个数据元素可能有多个直接前驱和多个直接后继。每个数据元素可能有多个直接前驱和多个直接后继。 图是比线性表和树复杂的数据结构，广泛应用于语图是比线性表和树复杂的数据结构，广泛应用于语言学、逻辑学、物理、化学等领域。言学、逻辑学、物理、化学等领域。Data StructureData StructurePage 52022-3-2q图的抽象数据类型定义如下：图的抽象数据类型定义如下：ADT ADT GraphGraph 数据对象数据对象V V ：V V是具有相同特性的数据元素的集合，称为顶是具有相同特性的数据元素的

4、集合，称为顶 点集。点集。数据关系数据关系R R ：R=VRR=VRVRVR| v,wV| v,wV且且P(v,w)P(v,w)，表示从表示从v v到到w w的的 弧，谓词弧，谓词P(v,w)P(v,w)定义了弧定义了弧的意义的意义 或信息或信息 Data StructureData StructurePage 62022-3-2G1=(G1=(V1V1, , VR1VR1) )V1 = A, B, C, D, EV1 = A, B, C, D, EVR1=,VR1=, , ,G2=(G2=(V2V2, , VR2VR2) )V2=A, B, C, D, E, FV2=A, B, C, D,

5、E, FVR2=(A,B),(A,E),(B,E),(C,D),VR2=(A,B),(A,E),(B,E),(C,D), (D,F),(B,F),(C,F) (D,F),(B,F),(C,F) Data StructureData StructurePage 72022-3-2CreateGraph(&G, V, VR);CreateGraph(&G, V, VR);初始条件：初始条件：V V 是图的顶点集，是图的顶点集，VR VR 是图中弧的集合。是图中弧的集合。操作结果：按操作结果：按 V V 和和 VR VR 的定义的定义构造图构造图 G G。DestroyGraph(&G);Destr

6、oyGraph(&G);初始条件：图初始条件：图 G G 存在。存在。操作结果：操作结果：销毁图销毁图 G G。LocateVex(G, u);LocateVex(G, u);初始条件：图初始条件：图 G G 存在，存在，u u 和和 G G 中顶点有相同特征。中顶点有相同特征。操作结果：若操作结果：若 G G 中存在和中存在和 u u 相同的顶点，则相同的顶点，则返回该顶点返回该顶点 在图中位置在图中位置；否则返回其它信息。；否则返回其它信息。Data StructureData StructurePage 82022-3-2GetVex(G, v);GetVex(G, v);初始条件：图初

7、始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：返回操作结果：返回 v v 的值的值。FirstAdjVex(G, v);FirstAdjVex(G, v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：返回返回 v v 的第一个邻接点。的第一个邻接点。若该顶点在若该顶点在 G G 中没中没 有邻接点，则返回有邻接点，则返回“空空”。NextAdjVex(G, v, w);NextAdjVex(G, v, w);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点

8、，中某个顶点，w w 是是 v v 的的 邻接顶点。邻接顶点。操作结果：操作结果：返回返回 v v 的（相对于的（相对于 w w 的）下一个邻接点。的）下一个邻接点。若若 w w 是是 v v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。Data StructureData StructurePage 92022-3-2PutVex(&G, v, value);PutVex(&G, v, value);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：对对 v v 赋值赋值 valuevalue。InsertVex(&

9、G, v);InsertVex(&G, v);初始条件：图初始条件：图 G G 存在，存在，v v 和图中顶点有相同特征。和图中顶点有相同特征。操作结果：在图操作结果：在图 G G 中中增添新顶点增添新顶点 v v。DeleteVex(&G, v);DeleteVex(&G, v);初始条件：图初始条件：图 G G 存在，存在，v v 是是 G G 中某个顶点。中某个顶点。操作结果：操作结果：删除删除 G G 中顶点中顶点 v v 及其相关的弧及其相关的弧。Data StructureData StructurePage 102022-3-2InsertArc(&G, v, w);Insert

10、Arc(&G, v, w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G 中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中增添弧增添弧，若，若 G G 是是无向的，则还无向的，则还 增添对称弧增添对称弧。DeleteArc(&G, v, w);DeleteArc(&G, v, w);初始条件：图初始条件：图 G G 存在，存在，v v 和和 w w 是是 G G 中两个顶点。中两个顶点。操作结果：在操作结果：在 G G 中中删除弧删除弧，若若 G G 是是无向的，则还无向的，则还 删除对称弧删除对称弧。Data StructureData St

11、ructurePage 112022-3-2DFSTraverse(G, Visit();DFSTraverse(G, Visit();初始条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图操作结果：对图 G G 进行进行深度优先深度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且仅一次。一旦一次且仅一次。一旦 visit() visit() 失败，则操作失败。失败，则操作失败。BFSTraverse(G, Visit();BFSTraverse(G, Visit();初始

12、条件：图初始条件：图 G G 存在，存在，Visit Visit 是顶点的应用函数。是顶点的应用函数。操作结果：对图操作结果：对图 G G 进行进行广度优先广度优先遍历。遍历过程中对每遍历。遍历过程中对每 个顶点调用函数个顶点调用函数Visit Visit 一次且仅一次。一旦一次且仅一次。一旦 visit() visit() 失败，则操作失败。失败，则操作失败。 ADT Graph ADT GraphData StructureData StructurePage 122022-3-2q 图的术语图的术语v图图(Graph)(Graph)：由两个集合：由两个集合V(G)V(G)和和E(G)E(

13、G)组成，记为组成，记为G=(V,E)G=(V,E)。V(G)V(G)是顶点的是顶点的非空非空有限集。有限集。E(G)E(G)是边的有限集合，边是顶点的无序对或有序对。是边的有限集合，边是顶点的无序对或有序对。v有向图有向图：由两个集合：由两个集合V(G)V(G)和和E(G)E(G)组成。组成。V(G)V(G)是顶点的非空有限集。是顶点的非空有限集。E(G)E(G)是是有向边有向边（也称弧）的有限集合，弧是顶点的（也称弧）的有限集合，弧是顶点的有序对有序对，记，记为为，v,wv,w是顶点，是顶点，v v为为弧尾弧尾，w w为为弧头弧头。v无向图无向图：由两个集合：由两个集合V(G)V(G)和和

14、E(G)E(G)组成。组成。V(G)V(G)是顶点的非空有限集。是顶点的非空有限集。E(G)E(G)是是无向边无向边的有限集合，边是顶点的的有限集合，边是顶点的无序对无序对，记为，记为（v,wv,w）或（或（w,v)w,v)，并且（，并且（v,w)=(w,v)v,w)=(w,v)。Data StructureData StructurePage 132022-3-2245136V(G1)=1,2,3,4,5,6V(G1)=1,2,3,4,5,6E(G1)=, ,E(G1)=, , , , , , 1573246V(G2)=1,2,3,4,5,6,7V(G2)=1,2,3,4,5,6,7E(G2

15、)=(1,2), (1,3), (2,3),E(G2)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (2,4),(2,5), (5,6), (5,7) (5,7)Data StructureData StructurePage 142022-3-2v无向完全图无向完全图：对：对n n个顶点的无向图，若每个顶点和其它个顶点的无向图，若每个顶点和其它n-1n-1个顶点都有个顶点都有 边，该图称为无向完全图。图中共有边，该图称为无向完全图。图中共有n(n-1)/2n(n-1)/2条边。条边。v有向完全图有向完全图：n n个顶点的有向图具有个顶点的有向图具有n(n

16、-1)n(n-1)条弧。条弧。v权权：与图的边或弧相关的数，可以表示从一个顶点到另一个顶点的距：与图的边或弧相关的数，可以表示从一个顶点到另一个顶点的距 离或耗费。离或耗费。v网网：带权的图。：带权的图。v稀疏（稠密）图稀疏（稠密）图：有很少（很多）条边或弧的图。：有很少（很多）条边或弧的图。v子图子图：对于图：对于图G G和图和图G G，若，若V(G) V(G) V V(G),(G),E E(G) (G) E E (G),(G),称称GG为为G G的子的子 图。图。Data StructureData StructurePage 152022-3-22 21 13 3无向完全图无向完全图2

17、21 13 3有向完全图有向完全图2 24 45 51 13 36 63 35 56 6图与子图图与子图Data StructureData StructurePage 162022-3-2v顶点的度顶点的度：无向图中，顶点的度为与每个顶点相连的边数。记作无向图中，顶点的度为与每个顶点相连的边数。记作TD(V)TD(V)。有向图中，顶点的度分成入度与出度。记作有向图中，顶点的度分成入度与出度。记作TD(V)TD(V)。入度：以该顶点为头的弧的数目。记作入度：以该顶点为头的弧的数目。记作ID(V)ID(V)。出度：以该顶点为尾的弧的数目。记作出度：以该顶点为尾的弧的数目。记作OD(V)OD(V)

18、。2 24 45 51 13 36 6G1G1顶点顶点2 2入度：入度：1 1 出度：出度：3 3顶点顶点4 4入度：入度：1 1 出度：出度：0 01 15 57 73 32 24 4G2G26 6顶点顶点5 5的度：的度：3 3顶点顶点2 2的度：的度：4 4Data StructureData StructurePage 172022-3-2v路径路径：顶点的序列：顶点的序列V=VV=Vi0i0,V,Vi1i1,V,Vinin ，满足，满足(V(Vij-1ij-1,V,Vijij) ) E E 或或 V E,(1jE,(1j n)n)。v路径长度路径长度：路径上边或弧的：路径上边或弧的数

19、目数目。v简单路径简单路径：序列中：序列中顶点不重复顶点不重复出现的路径。出现的路径。v回路回路：第一个第一个顶点和顶点和最后一个最后一个顶点顶点相同相同的路径。的路径。v简单回路简单回路：除了第一个顶点和最后一个顶点外，：除了第一个顶点和最后一个顶点外，其余顶点不重复其余顶点不重复 出现的回路。出现的回路。v连通连通：无向图无向图中，如果顶点中，如果顶点V V到顶点到顶点W W有路径，则有路径，则V V和和W W是连通的。是连通的。v连通图连通图：任意两个顶点都是连通的无向图。：任意两个顶点都是连通的无向图。v强连通图强连通图：有向图有向图中，每一对中，每一对V Vi i,V,Vj j V,

20、 V, V Vi i V Vj j, ,从从V Vi i到到V Vj j和从和从V Vj j到到 V Vi i都存在路径。都存在路径。v连通分量连通分量：无向图的极大连通子图。：无向图的极大连通子图。Data StructureData StructurePage 182022-3-21573246245136路径：路径：1 1，2 2，3 3，5 5，6 6，3 3路径长度：路径长度：5 5简单路径：简单路径：1 1，2 2，3 3，5 5回路：回路：1 1，2 2，3 3，5 5，6 6，3 3，1 1简单回路：简单回路：3 3，5 5，6 6，3 3路径：路径：1 1，2 2，5 5，7

21、 7，6 6，5 5，2 2，3 3路径长度：路径长度：7 7简单路径：简单路径：1 1，2 2，5 5，7 7，6 6回路：回路：1 1，2 2，5 5，7 7，6 6，5 5，2 2，1 1简单回路：简单回路：1 1，2 2，3 3，1 1Data StructureData StructurePage 192022-3-2连通图连通图2 24 45 51 13 36 6强连通图强连通图3 35 56 6非连通图非连通图2 24 45 51 13 36 6Data StructureData StructurePage 202022-3-2v生成树生成树一个含一个含 n n 个顶点的连通图

22、的生成树是该图中的一个个顶点的连通图的生成树是该图中的一个极小连通子图极小连通子图，它包含图中它包含图中 n n 个顶点个顶点和足以构成一棵树的和足以构成一棵树的 n-1 n-1 条边条边。v生成森林生成森林对于非连通图，对其每个连通分量可以构造一棵生成树，合成起来对于非连通图，对其每个连通分量可以构造一棵生成树，合成起来就是一个生成森林。就是一个生成森林。生成树生成树Data StructureData StructurePage 212022-3-2q 数组表示法数组表示法( (邻接矩阵邻接矩阵) )v将图的将图的顶点信息存储在一个一维数组中顶点信息存储在一个一维数组中，并将它的，并将它的

23、邻接矩阵存邻接矩阵存储在一个二维数组中储在一个二维数组中即构成图的数组表示。即构成图的数组表示。v假设图中顶点数为假设图中顶点数为n n，则邻接矩阵，则邻接矩阵A A定义为定义为，其它0E(G)v,v或)v,(v若1,jijijiA网的邻接矩阵的定义为，当网的邻接矩阵的定义为，当v vi i到到v vj j有弧相邻接时，有弧相邻接时，a aijij的值应为该的值应为该弧上的权值，否则为弧上的权值，否则为。Data StructureData StructurePage 222022-3-2v图的数组图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示#define INFINITY #defi

24、ne INFINITY INT_MAX; INT_MAX; / / 最大值最大值#define MAX_VERTEX_NUM #define MAX_VERTEX_NUM 20;20;/ / 最大顶点个数最大顶点个数typedef enum DG,DN,UDG,UDN GraphKind;typedef enum DG,DN,UDG,UDN GraphKind;/ / 有向图有向图, ,有向网有向网, ,无向图无向图, ,无向网无向网 typedef struct ArcCell typedef struct ArcCell VRType VRType adj; adj; / VRType/

25、VRType是顶点关系类型。对无权图，用是顶点关系类型。对无权图，用1 1或或0 0 / / 表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型。InfoType InfoType * *info; info; / / 该弧相关信息的指针该弧相关信息的指针 ArcCell, ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUMAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; ;typedef struct typedef struct VertexType VertexType vexsMAX_VERTEX

26、_NUMvexsMAX_VERTEX_NUM; ; / / 顶点信息顶点信息AdjMatrix AdjMatrix arcsarcs; ; / / 邻接矩阵邻接矩阵int int vexnum, arcnumvexnum, arcnum; ; / / 图的当前顶点数和弧图的当前顶点数和弧( (边边) )数数GraphKind GraphKind kindkind; ; / / 图的种类标志图的种类标志 MGraphMGraph; ;Data StructureData StructurePage 232022-3-2G1G1BDAC0 01 11 10 00 00 00 00 0G G1 1.

27、 .a ar rc cs s = =0 00 00 01 11 10 00 00 0G1.vexs=A,B,C,DG1.vexnum=4G1.arcnum=4G1.kind=DGData StructureData StructurePage 242022-3-2AECBDG2G20 01 10 01 10 01 10 01 10 01 1G G2 2. .a ar rc cs s = =0 01 10 01 11 11 10 01 10 00 00 01 11 10 00 0G2.vexs=A,B,C,D,EG2.vexnum=5G2.arcnum=6G2.kind=UDGData Stru

28、ctureData StructurePage 252022-3-2A AD DE EB BC C7 75 53 31 18 86 64 42 2G3G3G3.vexs=A,B,C,D,EG3.vexnum=5G3.arcnum=8G3.kind=UDN0 05 57 70 03 35 50 00 04 48 8G G3 3. .a ar rc cs s = =7 70 00 02 21 10 04 42 20 06 63 38 81 16 60 0Data StructureData StructurePage 262022-3-2v特点特点：无向图无向图的邻接的邻接矩阵对称矩阵对称，可，可

29、压缩存储压缩存储；有；有n n个顶点的无向图需个顶点的无向图需存储空间为存储空间为n(n+1)/2n(n+1)/2。有向图有向图邻接邻接矩阵不一定对称矩阵不一定对称；有；有n n个顶点的有向图需存储空间个顶点的有向图需存储空间为为n n。无向图无向图中顶点中顶点ViVi的度的度TD(Vi)TD(Vi)是邻接矩阵是邻接矩阵A A中第中第i i行元素之和行元素之和。有向图有向图中，中，顶点顶点ViVi的的出度是出度是A A中第中第i i行元素之和行元素之和。顶点顶点ViVi的的入度是入度是A A中第中第i i列元素之和列元素之和。v邻接矩阵的优缺点邻接矩阵的优缺点优点优点：容易判定顶点间有无边（弧

30、）和计算顶点的度（出度、：容易判定顶点间有无边（弧）和计算顶点的度（出度、 入度）。入度）。缺点缺点：边数较少时，空间浪费较大。：边数较少时，空间浪费较大。Data StructureData StructurePage 272022-3-2q 引入原因引入原因v邻接矩阵在稀疏图时空间浪费较大。邻接矩阵在稀疏图时空间浪费较大。q 实现实现v为图中为图中每个顶点建立一个单链表每个顶点建立一个单链表，第，第i i个单链表中的结点表示依个单链表中的结点表示依附于顶点附于顶点ViVi的边（有向图中指以的边（有向图中指以ViVi为尾的弧）。为尾的弧）。v每个链表附设一个表头结点每个链表附设一个表头结点。

31、表结点表结点adjvexadjvexnextarcnextarcinfoinfo与与ViVi邻接的邻接的点在表头数点在表头数组中的位置组中的位置头结点头结点datadatafirstarcfirstarcData StructureData StructurePage 282022-3-2#define MAX_VERTEX_NUM 20;#define MAX_VERTEX_NUM 20;typedef struct ArcNode typedef struct ArcNode int int adjvex; adjvex; / / 该弧所指向的顶点的位置该弧所指向的顶点的位置struct

32、ArcNode struct ArcNode * *nextarc;nextarc; / / 指向下一条弧的指针指向下一条弧的指针InfoType InfoType * *info;info; / / 该弧相关信息的指针该弧相关信息的指针 ArcNode; ArcNode; typedef struct VNode typedef struct VNode VertexType VertexType data;data;/ / 顶点信息顶点信息ArcNode ArcNode * *firstarc;firstarc; / / 指向第一条依附该顶点的弧指向第一条依附该顶点的弧 AdjListMA

33、X_VERTEX_NUMAdjListMAX_VERTEX_NUM; ;typedef struct typedef struct AdjList AdjList verticesvertices; ; / / 顶点数组顶点数组int vexnum, arcnum;int vexnum, arcnum; / / 图的当前顶点数和弧数图的当前顶点数和弧数int kind;int kind; / / 图的种类标志图的种类标志 ALGraphALGraph; ;Data StructureData StructurePage 292022-3-2ABLMCFDEGHKIJ邻接表邻接表12121111

34、10109 98 87 76 65 54 43 32 21 10 0M ML LK KJ JI IH HG GF FE ED DC CB BA A1152 112 0 0 4 3 0108 710 6 612 117 6129 0119 1Data StructureData StructurePage 302022-3-2G1G1bdac0123acdbdatafirstarc 2 1 3 0adjvex nextv特点特点无向图中顶点无向图中顶点ViVi的度为第的度为第i i个单链表中的结点数。个单链表中的结点数。有向图中有向图中顶点顶点ViVi的出度为第的出度为第i i个单链表中的结点个

35、数。个单链表中的结点个数。顶点顶点ViVi的入度为整个单链表中邻接点域值是的入度为整个单链表中邻接点域值是i i的结点个数。的结点个数。Data StructureData StructurePage 312022-3-2v优缺点优缺点优点优点：空间较省；无向图容易求各顶点的度；有向图容：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；易求顶点的出度；缺点缺点：求有向图顶点的入度则不容易，要遍历整个表。：求有向图顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。邻接点链接成单链表）。

36、bdac0123acdbdatafirstarc3 0 02adjvex next逆邻接表逆邻接表Data StructureData StructurePage 322022-3-2q 引入原因引入原因v对于同一个对于同一个有向图需要同时用邻接表和逆邻接表有向图需要同时用邻接表和逆邻接表时，不方便。时，不方便。G1G1bdac0123acdbdatafirstarc 2 1 3 0adjvex next邻接表邻接表Data StructureData StructurePage 332022-3-2q 引入原因引入原因v对于同一个对于同一个有向图需要同时用邻接表和逆邻接表有向图需要同时用邻接

37、表和逆邻接表时，不方便。时，不方便。q 实现实现v将在有向图的将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结邻接表和逆邻接表中两次出现的同一条弧用一个结点表示点表示，由于在邻接表和逆邻接表中的顶点，由于在邻接表和逆邻接表中的顶点数据数据是相同的，则在是相同的，则在十字链表中十字链表中只需要出现一次只需要出现一次，但需，但需保留分别指向第一条保留分别指向第一条 出弧出弧 和和第一条第一条 入弧入弧 的指针的指针。G1G1bdac逆邻接表逆邻接表0123acdbdatafirstarc3 0 02adjvex nextData StructureData StructurePage 34

38、2022-3-2弧结点弧结点tailvextailvex headvexheadvexhlinkhlinktlinktlinkinfoinfo顶点结点顶点结点datadatafirstinfirstinfirstoutfirstout弧尾弧尾位置位置弧头弧头位置位置弧头相同的下弧头相同的下一条弧指针一条弧指针弧相关信息弧相关信息的指针的指针指向该顶点指向该顶点第一条入弧第一条入弧指向该顶点指向该顶点第一条出弧第一条出弧Data StructureData StructurePage 352022-3-2 0 2 0 1 2 3 2 0 3 2 3 1 3 0bdacab cd0123求结点的入

39、度和求结点的入度和出度的方法？出度的方法？Data StructureData StructurePage 362022-3-2q 引入原因引入原因v无向图的邻接表中无向图的邻接表中每一条边有两个结点，每一条边有两个结点，给对图的边进行访问的给对图的边进行访问的操作带来不便。有些时候需要同时找到表示同一条边的两个结点操作带来不便。有些时候需要同时找到表示同一条边的两个结点（如删除一条边）。（如删除一条边）。aecbd0123acdbdatafirstarc 3 1 0 1adjvex next4e 3 2 4 0 42 12Data StructureData StructurePage 37

40、2022-3-2q 实现实现v每条边用一个结点表示。每条边用一个结点表示。边结点边结点markmarkivexivexilinkilinkjvexjvexjlinkjlinkinfoinfo顶点结点顶点结点markmarkfirstedgefirstedge访问访问标记标记边依附的边依附的一个顶点一个顶点边依附的边依附的另一个顶另一个顶点点依附这个顶依附这个顶点的下一条点的下一条边指针边指针依附这个顶依附这个顶点的下一条点的下一条边指针边指针访问访问标记标记指向第一条依指向第一条依附该顶点的边附该顶点的边Data StructureData StructurePage 382022-3-2ae

41、cbd0123acdb4e 0 1 0 3 2 3 2 1 2 4 4 1Data StructureData StructurePage 392022-3-2q 图的遍历图的遍历v从图中从图中某一顶点某一顶点出发，访问图中出发，访问图中其余顶点，其余顶点，使每个顶点被使每个顶点被访问一访问一次且只被访问一次次且只被访问一次。v可以从图中可以从图中任意一个顶点出发任意一个顶点出发进行遍历。进行遍历。v遍历中需解决的问题遍历中需解决的问题确定一搜索路径确定一搜索路径；确保确保每个顶点被访问到每个顶点被访问到；确保每个顶点确保每个顶点只能被访问一次只能被访问一次。v解决方法解决方法深度优先和广度优

42、先。深度优先和广度优先。设设辅助数组辅助数组visitedvisited，初始时，数组元素的值均为，初始时，数组元素的值均为0 0或或falsefalse，表示未被遍历，一旦遍历，就置为表示未被遍历，一旦遍历，就置为1 1或或truetrue。Data StructureData StructurePage 402022-3-2q 方法方法v从图的某一顶点从图的某一顶点V0V0出发，访问此顶点；出发，访问此顶点；v然后依次然后依次从从V0V0的未被访问的邻接点的未被访问的邻接点出发，出发，深度优先深度优先遍历图，直遍历图，直至图中至图中所有和所有和V0V0相通的顶点相通的顶点都被访问到；都被访

43、问到；v若此时若此时图中尚有顶点未被访问图中尚有顶点未被访问，则另选图中，则另选图中一个未被访问的顶一个未被访问的顶点作起点点作起点，重复上述过程，直至图中所有顶点都被访问为止。，重复上述过程，直至图中所有顶点都被访问为止。访问访问任意一个与任意一个与V0V0邻接的顶点邻接的顶点W1W1，再从，再从W1W1出发；出发；访问与访问与W1W1邻接且未被访问过的邻接且未被访问过的任意顶点任意顶点W2W2，再从，再从W2W2出发；出发；重复以上过程，直到重复以上过程，直到一个所有邻接点都被访问过的顶点一个所有邻接点都被访问过的顶点为止；为止；退回退回到到尚有邻接点未被访问过的顶点尚有邻接点未被访问过的

44、顶点，再从该顶点出发；，再从该顶点出发；直到所有的被访问过的顶点的邻接点都已被访问过为止。直到所有的被访问过的顶点的邻接点都已被访问过为止。Data StructureData StructurePage 412022-3-2V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V7V6V3V5V8V4V2V1V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V7V3V6V5V8V4V2V1Data StructureData StructurePage 422022-3-2V1V2V4V5V3V7V6V8

45、V5V7V6V3V8V4V2V1Data StructureData StructurePage 432022-3-2Boolen visitedMAX;Boolen visitedMAX;/访问标志数组访问标志数组Status (Status (* * visitFunc)(int v); visitFunc)(int v);/函数变量函数变量void DFSTraverse(Graph G, Status( void DFSTraverse(Graph G, Status( * * visit)(int v) visit)(int v)/ / 对图对图G G作深度优先遍历作深度优先遍历vi

46、sitFunc=visit;visitFunc=visit;/使用全局变量使用全局变量visitFunc visitFunc ， /使使DFSDFS不必设函数指针参数不必设函数指针参数for (v=0; vG.vexnum; +v)for (v=0; vG.vexnum; +v)visitedv = FALSE; visitedv = FALSE; / / 访问标识数组初始化访问标识数组初始化for (v=0; vG.vexnum; +v)for (v=0; v=0;w=NextAdjVex(G,v,w)for ( w=FirstAdjVex(G,v); w=0;w=NextAdjVex(G,

47、v,w)if (!visitedw) DFS(G, w);if (!visitedw) DFS(G, w); / / 对对v v的尚未访问过的邻接的尚未访问过的邻接/顶点顶点w w递归调用递归调用DFSDFS / DFS / DFSData StructureData StructurePage 452022-3-2V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1V10123V1V3V4V2data firstarc1 6 7 2adjvexnext4V55 3 0 4 0 1 7 1V6V7V8567 6 2 5 2 4 3V3V3 V7V7 V6V6 V2V2 V5V5 V8V8V

48、4V4Data StructureData StructurePage 462022-3-2V1V2V4V5V3V7V6V80123V1V3V4V2data firstarc 1 6 7 2adjvexnext4V5 5 3 7 1V6V7V8567 6深度遍历：深度遍历：V1V1V3V3 V7V7 V6V6 V2V2 V4V4 V8V8V5V5Data StructureData StructurePage 472022-3-2q 方法方法v从图的从图的某一顶点某一顶点V0V0出发，出发，访问访问此顶点后，依次此顶点后，依次访问访问V0V0的各个未曾的各个未曾访问过的邻接点访问过的邻接点；v

49、然后分别然后分别从这些邻接点出发从这些邻接点出发，广度优先遍历图，广度优先遍历图，直至图中所有已直至图中所有已被访问的顶点的邻接点都被访问到被访问的顶点的邻接点都被访问到；v若此时若此时图中尚有顶点未被访问图中尚有顶点未被访问，则，则另选图中一个未被访问的顶点另选图中一个未被访问的顶点作起点作起点，重复上述过程，重复上述过程，直至图中所有顶点都被访问为止直至图中所有顶点都被访问为止。 广度优先遍历的过程是以广度优先遍历的过程是以 v 为起始点，由近至为起始点，由近至远，依次访问和远，依次访问和 v 有路径相通且最短路径长度为有路径相通且最短路径长度为 1,2, 的顶点。的顶点。Data Str

50、uctureData StructurePage 482022-3-2V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V8V7V6V5V4V3V2V1V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8V8V7V6V5V4V3V2V1Data StructureData StructurePage 492022-3-2V1V2V4V5V3V7V6V8V5V8V7V6V4V3V2V1Data StructureData StructurePage 502022-3-2void BFSTraverse(vo

51、id BFSTraverse(Graph G, Status( Graph G, Status( * * visit)(int v) visit)(int v)/ / 对图对图G G进行广度优先搜索遍历进行广度优先搜索遍历for (v=0; vG.vexnum; +v) visitedv = FALSE; for (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q);InitQueue(Q);/ / 设置空队列设置空队列 Q Qfor ( v=0; vG.vexnum; +v )for ( v=0; v=0; w=NextAjdVex(G,u,

52、w) for ( w=FirstAdjVex(G,u); w=0; w=NextAjdVex(G,u,w) if (! visitedw ) if (! visitedw ) visitedw = TRUE; Visit(w);visitedw = TRUE; Visit(w);/ / 访问第访问第 w w 个顶点个顶点 EnQueue(Q, w); EnQueue(Q, w); / if/ if / while/ while / if/ if DestroyQueue(Q);DestroyQueue(Q); / BFSTraverse/ BFSTraverse1 12 23 34 45 56

53、 67 78 89 9101011111212Data StructureData StructurePage 512022-3-21423501231342data firstarc 4 4 3 2adjvexnext45 04 0 0 3 2 1 1Data StructureData StructurePage 522022-3-27.4.1 7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树q 无向图的连通分量无向图的连通分量v对于对于连通图连通图，仅需从图中，仅需从图中任一顶点出发任一顶点出发，进行，进行DFSDFS或或BFSBFS搜索，搜索，即即可遍历图的全部顶点可遍历图

54、的全部顶点；v对于对于非连通图非连通图，则需，则需从多个顶点从多个顶点出发进行出发进行DFSDFS或或BFSBFS搜索，才能搜索，才能遍遍历完图的全部顶点历完图的全部顶点。v每一次从一个新的起始点出发每一次从一个新的起始点出发进行进行DFSDFS或或BFSBFS搜索过程中搜索过程中所得的顶所得的顶点访问序列点访问序列就是各就是各连通分量的顶点集连通分量的顶点集。Data StructureData StructurePage 532022-3-2ABLMCFDEGHKIJ邻接表邻接表1212111110109 98 87 76 65 54 43 32 21 10 0M ML LK KJ JI

55、IH HG GF FE ED DC CB BA A1152 112 0 0 4 3 0108 710 6 612 117 6129 0119 1Data StructureData StructurePage 542022-3-2深度优先遍历的结果为深度优先遍历的结果为v从从A出发：出发：ALMJBFCv从从D出发：出发：DEv从从G出发：出发：GKHI连通分量：三个顶点集连通分量：三个顶点集+依附于这个顶点集中顶点的边。依附于这个顶点集中顶点的边。DEGHKIABLMCFJData StructureData StructurePage 552022-3-2q 生成树生成树v所有顶点均由边连

56、接在一起，但不存在回路的图称为生成树。所有顶点均由边连接在一起，但不存在回路的图称为生成树。一个有一个有n n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1n-1条边；条边；一个图可以有一个图可以有许多棵不同的生成树。许多棵不同的生成树。v对于连通图，对于连通图，调用调用DFSDFS所经过的边的集合所经过的边的集合和和图的全部顶点图的全部顶点构成了构成了图的极小连通子图，即连通图的一棵图的极小连通子图，即连通图的一棵深度优先生成树深度优先生成树。v对于连通图，对于连通图，调用调用BFSBFS所经过的边的集合所经过的边的集合和和图的全部顶点图的全部顶点构成了构成了图的极小连通子图，即连通

57、图的图的极小连通子图，即连通图的一棵一棵广度优先生成树广度优先生成树。v对于非连通图，每个连通分量的顶点集和所经过的边一起构成对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的若干棵生成树，这些连通图的生成树构成非连通图的生成森林生成森林。Data StructureData StructurePage 562022-3-2V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8深度遍历深度遍历V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树Data StructureData Structu

58、rePage 572022-3-2V V1 1V V2 2V V4 4V V5 5V V3 3V V7 7V V6 6V V8 8广度遍历广度遍历V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树Data StructureData StructurePage 582022-3-2ABLMCFDEGHKIJ深度优先遍历深度优先遍历：ABLMCFJDEGHKI深度优先生成森林深度优先生成森林Data StructureData StructurePage 592022-3-2q 问题描述问题描述v用一个连通网表示用一个连通网表示 n n 个居民点和各个居个居民点和各个居民点之间可能架设

59、的民点之间可能架设的通讯线路通讯线路，网中边，网中边上的权值表示架设这条线路所需上的权值表示架设这条线路所需经费经费。v在在 n n 个居民点间构建通讯网只需架设个居民点间构建通讯网只需架设 n-1 n-1 条线路，则工程队面临的问题是架条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？设哪几条线路能使总的工程费用最低？v问题均等价于：在含有问题均等价于：在含有 n n 个顶点的连通个顶点的连通网中选择网中选择 n-1 n-1 条边，构成一棵极小连通条边，构成一棵极小连通子图，并使该连通子图中子图，并使该连通子图中 n-1 n-1 条边上权条边上权值之和达到最小，则称这棵连通子图

60、为值之和达到最小，则称这棵连通子图为连通网的连通网的最小生成树最小生成树。v类似此类的问题很多。类似此类的问题很多。16543271317918127524101654327139510Data StructureData StructurePage 602022-3-2q 方法一：克鲁斯卡尔方法一：克鲁斯卡尔(Kruskal)(Kruskal)算法算法v基本思想基本思想为使生成树上总的权值之和达到最小，则应使为使生成树上总的权值之和达到最小，则应使每一条边上的权每一条边上的权值尽可能地小值尽可能地小，自然应从权值最小的边选起，直至选出，自然应从权值最小的边选起，直至选出 n-1 n-1 条互