图的定义和术语

1、第 1 页第 2 页 第七章第七章 图图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及应用7.6 最短路径 第 3 页第七第七 章章 图图本章介绍另一种非线性数据结构本章介绍另一种非线性数据结构 图图 图：是一种多对多的结构关系，每个元素可以有图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；零个或多个直接前趋；零个或多个直接后继；第 4 页第七第七 章章 图图 学习要点学习要点1熟悉图的各种存储结构及其构造算法，了解实际问题的求熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法

2、有密切联系；解效率与采用何种存储结构和算法有密切联系；2熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略遍历是一种广度优先搜索策略3理解课件中讨论的各种图的算法；理解课件中讨论的各种图的算法；第 5 页7.1 7.1 图的定义和术语图的定义和术语一一 图的概念图的概念 图图G G由两个集合构成，记作由两个

3、集合构成，记作G= G= 其中其中V V是顶点的非空有限集合，是顶点的非空有限集合，E E是边的有限集合，其中边是顶点的无序对或有序对集合。是边的有限集合，其中边是顶点的无序对或有序对集合。例例 G1=G1=V1=vV1=v1 1,v,v2 2, ,v v3 3, ,v v4 4 ,v,v5 5 E1=(vE1=(v1 1,v,v2 2),),(v(v1 1,v,v3 3),),(v(v2 2,v,v3 3),),(v(v2 2,v,v5 5),),(v(v3 3,v,v4 4),),(v(v3 3,v,v5 5) ) G1G1图示图示无序对无序对(v(vi i,v,vj j) )：用表示顶点

4、用表示顶点v vi i、v vj j的线段的线段，称为无向边；，称为无向边； V5V5 V1 V1 V2V2 V4V4 V3V3第 6 页7.1 7.1 图的定义和术语图的定义和术语例例 G2=G2=V2=vV2=v1 1,v,v2 2, ,v v3 3, ,v v4 4 E2=vE2=, , , , , , G2图示有序对有序对v ：用以表示以用以表示以v vi i起点、以起点、以v vj j为终点的有向线段，为终点的有向线段，称为有向边或弧；称为有向边或弧；无向图：无向图：在图在图G G中，若所有边是无向边，则称中，若所有边是无向边，则称G G为无向图；为无向图；有向图：有向图：在图在图G

5、 G中，若所有边是有向边，则称中，若所有边是有向边，则称G G为有向图；为有向图；混和图：混和图：在图在图G G中，即有无向边也有有向边，则称中，即有无向边也有有向边，则称G G为混合图；为混合图； V1V1 V2V2 V3V3 V4V4V1V1称为弧尾称为弧尾( (初始点初始点) )V3V3称为弧头称为弧头( (终端点终端点) )第 7 页7.1 7.1 图的定义和术语图的定义和术语图的应用举例例例1 1 交通图（公路、铁路）交通图（公路、铁路） 顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示交通图中的有单行道双行道，分别用有向

6、边、无向边表示；例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地点间的连线例例4 4 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 V5V5 V1 V1 V2V2 V4V4 V3V3第 8 页7.1 7.1 图的定义和术语图的定义和术语三 图的基本操作1 CreateGraph(&G, V, VR);1 CreateGraph(&G, V, VR);初始条件：初始条件：V V是图的顶点

7、集，是图的顶点集，VRVR是图中弧的集合是图中弧的集合操作结果：按操作结果：按V V和和VRVR的定义构造图的定义构造图G G2 DestroyGraph(&G);2 DestroyGraph(&G);初始条件：图初始条件：图G G存在存在操作结果：销毁图操作结果：销毁图G G3 LocateVex(G,u);3 LocateVex(G,u);初始条件：图初始条件：图G G存在，存在，u u和和G G中顶点有相同特征中顶点有相同特征操作结果：若操作结果：若G G中存在顶点中存在顶点u u，则返回该顶点在图中位置；否则返回其它则返回该顶点在图中位置；否则返回其它信息。信息。4 GetVex(G,

8、 v);4 GetVex(G, v);初始条件：图初始条件：图G G存在，存在，v v是是G G中某个顶点中某个顶点操作结果：返回操作结果：返回v v的值的值5 PutVex(&G, v, value);5 PutVex(&G, v, value);初始条件：图初始条件：图G G存在，存在，v v是是G G中某个顶点中某个顶点操作结果：对操作结果：对v v赋值赋值valuevalue第 9 页7.1 7.1 图的定义和术语图的定义和术语6 FirstAdjVex(G, v);6 FirstAdjVex(G, v);初始条件：图初始条件：图G G存在，存在，v v是是G G中某个顶点中某个顶点操

9、作结果：返回操作结果：返回v v的第一个邻接顶点。若顶点在的第一个邻接顶点。若顶点在G G中没有邻接顶点，则返中没有邻接顶点，则返回回“空空”。7 NextAdjVex(G, v, w);7 NextAdjVex(G, v, w);初始条件：图初始条件：图G G存在，存在，v v是是G G中某个顶点，中某个顶点，w w是是v v的邻接顶点。的邻接顶点。操作结果：返回操作结果：返回v v的（相对于的（相对于w w的）下一个邻接顶点。若的）下一个邻接顶点。若w w是是v v的最后一个的最后一个邻接点，则返回邻接点，则返回“空空”。8 InsertVex(&G, v);8 InsertVex(&G,

10、 v);初始条件：图初始条件：图G G存在，存在，v v和图中顶点有相同特征。和图中顶点有相同特征。操作结果：在图操作结果：在图G G中增添新顶点中增添新顶点v v9 DeleteVex(&G, v);9 DeleteVex(&G, v);初始条件：图初始条件：图G G存在，存在，v v和图中顶点有相同特征和图中顶点有相同特征操作结果：删除操作结果：删除G G中顶点中顶点v v及相关的弧及相关的弧第 10 页7.1 7.1 图的定义和术语图的定义和术语10 InsertArc(&G, v, w); 10 InsertArc(&G, v, w); 初始条件：图初始条件：图G G存在，存在，v v

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

12、：图初始条件：图G G存在，存在，v v是是G G中某个顶点，中某个顶点，VisitVisit是顶点的应用函数。是顶点的应用函数。操作结果：从顶点操作结果：从顶点v v起深度优先遍历图起深度优先遍历图G G，对每个顶点调用函数对每个顶点调用函数VisitVisit一次一次且仅一次。一旦且仅一次。一旦visit( )visit( )失败，则操作失败失败，则操作失败13 BFSTraverse(G, v, Visit( );13 BFSTraverse(G, v, Visit( );初始条件：图初始条件：图G G存在，存在，v v是是G G中某个顶点，中某个顶点，VisitVisit是顶点的应用函

13、数。是顶点的应用函数。操作结果：从顶点操作结果：从顶点v v起广度优先遍历图起广度优先遍历图G G，对每个顶点调用函数对每个顶点调用函数VisitVisit一次一次且一次。一旦且一次。一旦visit( )visit( )失败，则操作失败失败，则操作失败第 11 页7.1 7.1 图的定义和术语图的定义和术语图的基本术语图的基本术语1 1 邻接点及关联边邻接点及关联边 邻接点：邻接点：边的两个顶点边的两个顶点 关联边：关联边：若边若边e= (v, ue= (v, u), ), 则称顶点则称顶点v v、u u 关联边关联边e e （边边e e 依附于顶点依附于顶点v,u)v,u)2 2 顶点的度、

14、入度、出度顶点的度、入度、出度 顶点顶点V V的度的度= =与与V V相关联的边的数目相关联的边的数目 在有向图中：在有向图中： 顶点顶点V V的出度的出度= =以以V V为起点有向边数为起点有向边数 顶点顶点V V的入度的入度= =以以V V为终点有向边数为终点有向边数 顶点顶点V V的度的度= = V V的出度的出度+ +V V的入度的入度 设图设图G G的顶点数为的顶点数为n n，边数为边数为e e 图的所有顶点的度数和图的所有顶点的度数和 = 2 = 2* *e e （每条边对图的所有顶点的度数和（每条边对图的所有顶点的度数和“贡献贡献”2”2度）度） e1e1 V1V1 V2V2 V

15、3V3 V4V4 V5V5 V1 V1 V2V2 V4V4 V3V3第 12 页3 有向完全图、有向完全图、无向完全图无向完全图有向完全图有向完全图n个顶点的有向图最大边数是个顶点的有向图最大边数是n(n-1)无向完全图无向完全图n个顶点的无向图最大边数是个顶点的无向图最大边数是n(n-1)/2权权(weight)与图的边或弧相关的数叫与图的边或弧相关的数叫网网带权的图叫带权的图叫7.1 图的图的定义和术语定义和术语第 13 页7.1 7.1 图的定义和术语图的定义和术语 路径、回路路径、回路 无向图中的顶点序列无向图中的顶点序列v1,v2, ,vk,v1,v2, ,vk,若若( (vi,vi

16、+1)vi,vi+1) E( i=1,2,k-1), E( i=1,2,k-1), v =v1, u =vk,v =v1, u =vk, 则称该序列是从顶点则称该序列是从顶点v v到顶点到顶点u u的的路径路径；若；若v=uv=u，则称则称该序列为该序列为回路回路； 有向图有向图D=(V，E）中的顶点序列中的顶点序列v1,v2, ,vk, v1,v2, ,vk, 若若 vi,vi+1 E E ( i=1,2,k-1), v =v1, u =vk, ( i=1,2,k-1), v =v1, u =vk, 则称该序列是从顶点则称该序列是从顶点v v到顶点到顶点u u的路的路径；若径；若v=uv=u

17、，则称该序列为回路；则称该序列为回路； 例例 在图在图1 1中，中，V1,V2V1,V2, ,V3,V4 V3,V4 是是V1V1到到V4V4的路径；的路径； V1,V2 V1,V2, ,V3,V4,V1V3,V4,V1是回路；是回路；在图在图2 2中，中，V1,V3V1,V3, ,V4 V4 是是V1V1到到V4V4的路径；的路径； V1,V3,V4,V1 V1,V3,V4,V1是回路；是回路； V5V5 V1 V1 V2V2 V4V4 V3V3 V1V1 V2V2 V3V3 V4V4图1图2第 14 页7.1 7.1 图的定义和术语图的定义和术语连通图、（强连通图）连通图、（强连通图） 在

18、无（有）向图在无（有）向图G=G=中，若对任何两个顶点中，若对任何两个顶点v v、u u都存在从都存在从v v到到u u的路径，则称的路径，则称G G是连通图（强连通图）是连通图（强连通图） V5V5 V6V6 V3V3 V1V1 V2V2 V4V4连通图连通图非连通图非连通图 V5V5 V1 V1 V2V2 V4V4 V3V3第 15 页7.1 7.1 图的定义和术语图的定义和术语子图子图 设有两个图设有两个图G=（V，E）、）、G1=（V1，E1），），若若V1 V，E1 E，E1关联的顶点都在关联的顶点都在V1中，则称中，则称 G1是是G的子图；的子图；例例 图图2、图、图3 是是 图图

19、1 的子图的子图 V5V5 V1 V1 V2V2 V4V4 V3V3 V5V5 V1 V1 V2V2 V3V3 V5V5 V1 V1 V2V2 V4V4 V3V3图图1 1图图2 2图图3 3第 16 页7.1 7.1 图的定义和术语图的定义和术语连通分图（强连通分量） 无向图无向图G的极大连通子图称为的极大连通子图称为G的连通分量的连通分量 极大连通子图意思是：该子图是极大连通子图意思是：该子图是G连通子图，将连通子图，将G的任何不在该子图的任何不在该子图中的顶点加入，子图不再连通；中的顶点加入，子图不再连通； 有向图有向图D的极大强连通子图称为的极大强连通子图称为D的强连通分量的强连通分量

20、 极大强连通子图意思是：该子图是极大强连通子图意思是：该子图是D强连通子图，将强连通子图，将D的任何不在该的任何不在该子图中的顶点加入，子图不再是强连通的；子图中的顶点加入，子图不再是强连通的； V5V5 V6V6 V3V3 V1V1 V2V2 V4V4连通分图连通分图第 17 页7.1 7.1 图的定义和术语图的定义和术语 V5V5 V1 V1 V2V2 V4V4 V3V3 V5V5 V1 V1 V2V2 V4V4 V3V38 生成树（ 包含无向图包含无向图G所有顶点的的极小连通子图称为所有顶点的的极小连通子图称为G生成树生成树 极小连通子图意思是：该子图是极小连通子图意思是：该子图是G的连

21、通子图，在该子图中删除任的连通子图，在该子图中删除任何一条边，子图不再连通，何一条边，子图不再连通， 若若T是是G的生成树当且仅当的生成树当且仅当T满足如下条件满足如下条件 T是是G的连通子图的连通子图 T包含包含G的所有顶点的所有顶点 T中无回路中无回路 只有足以构成一棵树的只有足以构成一棵树的n-1条边条边第 18 页例213213有向完全图有向完全图无向完全图无向完全图356例245136图与子图图与子图例245136G1顶点顶点2入度：入度：1 出度：出度：3顶点顶点4入度：入度：1 出度：出度：0例157324G26顶点顶点5的度：的度：3顶点顶点2的度：的度：4第 19 页例157

22、324G26例245136G1路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，3路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，1第 20 页连通图连通图例245136强连通图强连通图356例非连通图连通分量非连通图连通分量例245136第 21 页第七第七 章章 图图 7.2 7.2 图的存储结构图的存储结构数组表示法1邻接表第 22 页7.2 7.2 图

23、的存储结构图的存储结构 图是多对多的结构，比线性结构、树结构复杂，所以其存储结构也图是多对多的结构，比线性结构、树结构复杂，所以其存储结构也要复杂些。与线性结构、树结构一样，图的存储结构至少要保存两类信要复杂些。与线性结构、树结构一样，图的存储结构至少要保存两类信息：息：1)1)顶点的数据顶点的数据 2) 2)顶点间的关系顶点间的关系顶点的编号顶点的编号 为了使图的存储结构与图一一对应，在讨论图的存储结构时，首先为了使图的存储结构与图一一对应，在讨论图的存储结构时，首先要给图的所有顶点编号。要给图的所有顶点编号。 本课程介绍两类图的存储结构本课程介绍两类图的存储结构数组表示法数组表示法邻接表（

24、邻接表，逆邻接表）邻接表（邻接表，逆邻接表） 设设 G=G=是图是图, , V=v V=v1 1,v,v2 2, ,v v3 3, , v vn n , ,设顶点的的设顶点的的角标为它的编号 如何表示顶点间的关系？第 23 页7.2 7.2 图的存储结构图的存储结构 邻接矩阵邻接矩阵：G G的邻接矩阵是满足如下条件的的邻接矩阵是满足如下条件的n n阶矩阵：阶矩阵： 一一 数组表示法数组表示法数组表示法是图的一种顺序存储结构数组表示法是图的一种顺序存储结构在数组表示法中，用邻接矩阵表示顶点间的关系在数组表示法中，用邻接矩阵表示顶点间的关系Aij=Aij=1 1 若若( (vi,vi+1)vi,v

25、i+1) E E 或或 vi,vi+1 E E0 0 否则否则 V5V5 V1 V1 V2V2 V4V4 V3V30 1 0 1 00 1 0 1 00 1 0 10 1 0 10 1 0 1 10 1 0 1 10 1 0 00 1 0 01 10 1 1 0 00 1 1 0 00 1 1 00 1 1 00 0 0 00 0 0 00 0 0 10 0 0 1 0 0 00 0 0 V1V1 V2V2 V3V3 V4V4第 24 页7.2 7.2 图的存储结构图的存储结构数组表示法顶点的存储：用一维数组存储（按编号顺序）顶点间关系：用二维数组存储图的邻接矩阵；0 01 12 23 34

26、45 5m-1V1V1V2V2V3V3V4V4V5V5存储顶点的一维数组存储邻接矩阵的二维数组0 01 10 01 10 01 10 01 10 01 10 01 12 23 34 4mm+1m+2m+3m+4第 25 页7.2 7.2 图的存储结构图的存储结构数组表示法类型定义#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enumDG, DN, AG, AN GraphKind;typedef struct ArcCell VRType adj; InfoType *info;ArcCell, AdjMatrixMAX_VE

27、RTEX_NUM MAX_VERTEX_NUM typedef struct VetexType vexsMAX_VERTEX_NUM ; AdjMatrix arc; int vexnum, arcnum; GraphKind kind;MGraph;第 26 页7.2 7.2 图的存储结构图的存储结构设G是Mgraph 类型的变量，用于存储无向图，该图有n个顶点，e条边G的图示如下：G.vexs G.arcs G.vexnumG.arcnu G.kind V1V10 0n ne eAGAG顶点数组存储邻接矩阵的二维数组第 27 页7.2 7.2 图的存储结构图的存储结构无向图数组表示法特点

28、：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点v的度：等于二维数组对应行（或列）中1的个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；5）设存储顶点的一维数组大小为m(m图的顶点数n), G占用存储空间：m+m2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；对有向图的数组表示法可做类似的讨论第 28 页7.2 7.2 图的存储结构图的存储结构邻接表 邻接表是图的链式存储结构1 无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存

29、储 V5V5 V1 V1 V2V2 V4V4 V3V3例 0 0 1 1 2 2 3 3 4 4m-1m-1V1V1V2V2V3V3V4V4V5V51 13 34 42 22 21 11 10 00 04 43 3该结点表示边（V1 V2）,其中的1是V2在一维数组中的位置第 29 页7.2 7.2 图的存储结构图的存储结构图的邻接表类型定义#define MAX_VERTEX_NUM 20typedef struct ArcNode /边（弧）结点的类型定义边（弧）结点的类型定义int adjvex; /边（弧）的另一顶点的在数组中的位置边（弧）的另一顶点的在数组中的位置struct Arc

30、Node *nextarc; /指向下一条边（弧）结点的指针指向下一条边（弧）结点的指针InfoType *info;ArcNode;typedef struct VNode /顶点结点和数组的类型定义顶点结点和数组的类型定义VertexType data; /顶点信息顶点信息ArcNode * finrstarc; /指向关联该顶点的边（弧）链表指向关联该顶点的边（弧）链表VNode, AjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum, arcnum; /图的当前顶点数和弧数图的当前顶点数和弧数int kind;

31、/图的种类标志图的种类标志ALGraph;第 30 页7.2 7.2 图的存储结构图的存储结构设G是ALGraph 类型的变量，用于存储无向图G1，该图有n个顶点，e条边G的图示如下： V5V5 V1 V1 V2V2 V4V4 V3V3无向图G1该结点表示边（V5,V2）,其中的1是V2在一维数组中的位置G.vertices G.vexnum G.arcnu G.kind 0 0 1 1 2 2 4 4m-1m-1V1V1V2V2V3V3V4V4V5V5n ne eAGAG1 13 34 42 22 21 11 10 00 04 43 3data firstarcadjvex nextarc第

32、 31 页7.2 7.2 图的存储结构图的存储结构无向图的邻接表的特点 1）在G邻接表中，同一条边对应两个结点； 2）顶点v的度：等于v对应线性链表的长度； 3）判定两顶点v ，u是否邻接：要看v对应线性链表中有无对应的结点 4）在G中增减边：要在两个单链表插入、删除结点； 第 32 页7.2 7.2 图的存储结构图的存储结构D.vertices D.vexnum D.arcnu D.kind V V1 1V V2 2V V3 3V V4 4n ne eDGDG1 12 23 30 0 V1V1 V2V2 V3V3 V4V4例2 有向图的邻接表和逆邻接表1）有向图的邻接表顶点：用一维数组存储（

33、按编号顺序）以同一顶点为起点的弧：用线性链表存储类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储第 33 页7.2 7.2 图的存储结构图的存储结构2）有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储表类似于无向图的邻接表，所不同的是：以同一顶点为终点的弧：用线性链表存储D.vertices D.vexnum D.arcnu D.kind V V1 1V V2 2V V3 3V V4 4n ne eDGDG0 00 02 23 3 V1V1 V2V2 V3V3 V4V4第 34 页7.2 7.2 图的存储结构图的存储结构 在不同的存储

34、结构下，实现各种操作的效率可能是不同的。所以在求解实际问题时，要根据求解问题所需操作，选择合适的存储结构。第 35 页第七第七 章章 图图 7.3 7.3 图的遍历图的遍历一 深度优先遍历二 广度优先遍历第 36 页7.3 7.3 图的遍历图的遍历 图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。 图中可能有回路，遍历可能沿回路又回到已遍历过的结点。为避免同一顶点被多次访问，必须为每个被访问的顶点作一标志。为此引入一辅助数组， 记录每个顶点是否被访问过。 有两种遍历方法（它们对无向图，有向图都适用）： 深度优先遍历 广度优先遍历第 37 页7.3 7.3 图的遍历图的遍历

35、一一 深度优先遍历深度优先遍历从图中某顶点从图中某顶点v v出发：出发： 1 1）访问顶点）访问顶点v v；2 2）从从v v的未被访问的邻接点出发，继续对图进行深度优先遍历；的未被访问的邻接点出发，继续对图进行深度优先遍历；例例 图图G G中，以中，以V1V1起点的的深度优先序列：起点的的深度优先序列： （1 1） V1,V2,V4,V5,V8,V3,V6,V7,V1,V2,V4,V5,V8,V3,V6,V7, （2 2） V1,V2,V5,V8,V4,V3,V6,V7 V1,V2,V5,V8,V4,V3,V6,V7 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1

36、V1由于没为有规定由于没为有规定访问邻接点的顺序，访问邻接点的顺序，深度优先序列不是唯一的深度优先序列不是唯一的这是序列（1）在遍历过程中所经过的路径注：为简单起见，只讨论非空连通图的遍历第 38 页7.3 7.3 图的遍历图的遍历深度优先遍历( (设图为非空连通图）设图为非空连通图）从图中某顶点从图中某顶点v v出发：出发： 1 1）访问顶点）访问顶点v v；2 2）从从v v的未被访问的邻接点出发，的未被访问的邻接点出发，继续对图进行深度优先遍历；继续对图进行深度优先遍历； 先序遍历（先序遍历（D DL LR R） 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）

37、先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树）先序遍历右子树；如果将图顶点的邻接点如果将图顶点的邻接点看作二叉树结点的左、右孩子看作二叉树结点的左、右孩子深度优先遍历与深度优先遍历与先序遍历先序遍历是不是很类似？是不是很类似？ V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1第 39 页7.3 7.3 图的遍历图的遍历深度优先遍历算法深度优先遍历算法void DFS(Graph G, int v, Status(*Visit(int v) / 从第从第v个顶点出发，递归地深度优先遍历图个顶点出发，递归地深度优先遍历图G。 / v是顶点在一维数组中的

38、位置，是顶点在一维数组中的位置，假设假设G G是非空图是非空图visitedv =TRUE; Visit(v); /访问第访问第v个顶点个顶点for (w= FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w)if (!visitedw) DFS(G, w); /对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFSBoolean visitedMAX_VERTEX_NUMBoolean visitedMAX_VERTEX_NUM /访问标志数组访问标志数组, ,全局变量，初始值：所有分量全为全局变量，初始值：所有分量全为False(0)Fal

39、se(0)/visitedv=TRUE/visitedv=TRUE表示顶点表示顶点v v已被访问已被访问visited01234m-100000第 40 页7.3 7.3 图的遍历图的遍历先序遍历递归算法先序遍历递归算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /本算法先序遍历以本算法先序遍历以T为根结点指针的二叉树。为根结点指针的二叉树。 if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrde

40、rTraverse(T-rchild, Visit); /PreOrderTraverse如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历算法与先序遍历算法的结构是不是很像？深度优先遍历算法深度优先遍历算法void DFS(Graph G, int v, Status(*Visit(int v) / 从第从第v个顶点出发，递归地深度优先遍历图个顶点出发，递归地深度优先遍历图G。 / v是顶点在一维数组中的位置，是顶点在一维数组中的位置，假设假设G G是非空图是非空图visitedv =TRUE; Visit(v); /访问第访问第v个顶点个顶点for (w= FirstAdjVex(

41、G, v); w; w=NextAdjVex(G, v, w)if (!visitedw) DFS(G, w); /对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w递归调用递归调用DFS第 41 页7.3 7.3 图的遍历图的遍历广度优先遍历（类似于树的按层遍历）广度优先遍历（类似于树的按层遍历） 从图中某顶点从图中某顶点v v出发：出发：1 1）访问顶点）访问顶点v v ；2 2）访问）访问v v的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , , wwk k ；3 3）依次依次从这些邻接点出发，访问它们的所有未被访问的邻接点从这些邻接点出发，访问它们的所有未被

42、访问的邻接点; ; 依依此类推，直到图中所有访问过的顶点的邻接点都被访问；此类推，直到图中所有访问过的顶点的邻接点都被访问；例例 图图G G中，以中，以V1V1起点的的广度优先序列：起点的的广度优先序列： （1 1）V1,V1,V2,V3V2,V3, ,V4,V5,V6,V7,V8V4,V5,V6,V7,V8 （2 2）V1,V1,V3,V2V3,V2, ,V6,V7,V4,V5,V8V6,V7,V4,V5,V8 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1这是序列（这是序列（1 1）在遍历过程中在遍历过程中所经过的路径所经过的路径由于没为有规定由于没为有规定

43、访问邻接点的顺序，访问邻接点的顺序，广度优先序列不是唯一的广度优先序列不是唯一的第 42 页7.3 7.3 图的遍历图的遍历广义优先遍历算法广义优先遍历算法从图中某顶点从图中某顶点v v出发：出发：1 1）访问顶点）访问顶点v v ；（；（容易实现）容易实现）2 2）访问）访问v v的所有未被访问的邻接点的所有未被访问的邻接点w w1 1 ,w ,w2 2 , , wwk k ； （容易实现）容易实现）3 3）依次从依次从这些邻接点这些邻接点（在步骤（在步骤 2 2）访问的顶点）出发，访问它们的所有）访问的顶点）出发，访问它们的所有未被访问的邻接点未被访问的邻接点; ; 依此类推，直到图中所有

44、访问过的顶点的邻接点都依此类推，直到图中所有访问过的顶点的邻接点都被访问；被访问；为实现为实现 3 3），需要保存在步骤），需要保存在步骤(2(2）中访问的顶点，而且）中访问的顶点，而且访问这些顶点访问这些顶点邻邻接点接点的顺序为：先保存的顶点，其邻接点先被访问。的顺序为：先保存的顶点，其邻接点先被访问。在在广度优先遍历算法中，需设置一队列广度优先遍历算法中，需设置一队列Q Q，保存已访问的顶点，并控制遍历顶点的顺序。保存已访问的顶点，并控制遍历顶点的顺序。第 43 页7.3 7.3 图的遍历图的遍历void BFSTraverse(Graph G,int v,Status (void BFS

45、Traverse(Graph G,int v,Status (* * Visit)(int v) Visit)(int v) /从从v v出发，广度优先遍历连通图出发，广度优先遍历连通图G G。 v是顶点在一维数组中的位置，是顶点在一维数组中的位置，使使用辅助队列用辅助队列Q Q和访问标志数组和访问标志数组visitedvisited。 for (u=0; u G.vexnum; +u) visitedu=FALSE; for (u=0; ulchild=p; first=FALSE; else /*w是是v的其它未被访问的邻接顶点，作为上一邻接顶点的右兄弟的其它未被访问的邻接顶点，作为上一邻

46、接顶点的右兄弟*/ q-nextsibling=p; q=p; DFSTree(G,w,&q); /*从第从第w个顶点出发深度优先遍历图个顶点出发深度优先遍历图G，建立生成子树，建立生成子树*q*/ 7.4 7.4 图的连通性图的连通性7.4.3 最小生成树最小生成树n个城市之间个城市之间,最多可能设置最多可能设置n(n-1)/2条线路条线路,而连通而连通n个城市只需个城市只需要要n-1条线路条线路. 最小最小(代价代价)生成树的定义生成树的定义. 一棵生成树的代价一棵生成树的代价.7.4 7.4 图的连通性图的连通性最小生成树最小生成树MST的性质的性质: 假设假设N=(V,E)是一个连通网

47、是一个连通网,U是顶点集是顶点集V的一个非空子集的一个非空子集.若若(u,v)是一条具有最小权是一条具有最小权值值(代价代价)的边的边,其中其中u属于属于U,v属于属于V-U,则必存则必存在一棵包含边在一棵包含边(u,v)的最小生成树的最小生成树.7.4 7.4 图的连通性图的连通性算法一：（普里姆算法）算法一：（普里姆算法） 假设假设N=(V,E)是连通网是连通网,TE是是N上最小生成树上最小生成树中边的集合中边的集合.算法从算法从U=u0(u0属于属于V),TE=开始开始,重复执行下述操作重复执行下述操作: 在所有在所有u属于属于U,v属于属于V-U的边的边(u,v)属于属于E中找中找一条

48、代价最小的边一条代价最小的边(u0,v0)并入集合并入集合TE,同时同时v0并入并入U,直至直至U=V为止为止. 此时此时TE中必有中必有n-1条边条边,则则T=(V,TE)为为N的最的最小生成树小生成树. 为实现这个算法需要附设一个辅助数组为实现这个算法需要附设一个辅助数组closedge,以记录从以记录从U到到V-U具有最小代价的边具有最小代价的边. 对每个顶点对每个顶点vi属于属于V-U,在辅助数组中存在一个在辅助数组中存在一个相应分量相应分量closedgei-1,它包括两个域它包括两个域, 其中其中lowcost存储该边上的权存储该边上的权.显然显然:closedgei-1.lowc

49、ost=Mincost(u,vi)|u属于属于U vex域存储该边依附的在域存储该边依附的在U中的顶点中的顶点.7.4 7.4 图的连通性图的连通性普里姆算法构造最小生成树的过程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4 7.4 图的连通性图的连通性普里姆算法普里姆算法void MiniSpanTree_PRIM（MGraph G，VertexType u） /用普里姆算法从第用普里姆算法从第u个顶点出发构造网个顶点出发构造网G的最小生成树的最小生成树T， /输出输出T的各条边。的各条边。 /记录从顶点集记录从顶点集U到到V-U的代价最小的边的辅

50、助数组定义：的代价最小的边的辅助数组定义：struct VertexType adjvex； VRType lowcost； closedgeMAX_VERTEX_NUM;7.4 7.4 图的连通性图的连通性k=LocateVex（G，u）；）；for（j=0；jG.vexnum；+j） /辅助数组初始化辅助数组初始化 if（j！=k）closedgej=u，G.arcskj.adj； /adjvex，lowcostclosedgek.lowcost=0； / 初始，初始，U=ufor（i=1；i0，vi V-U printf（closedgek.adjvex，G.vexsk）；）； /输出生

51、成树的边输出生成树的边 closedgek.lowcost=0； /第第k顶点并入顶点并入U集集 for（j=0；jG.vexnum；+j） if（G.arcskj.adjclosedgej.lowcost） /新顶点并入新顶点并入U后重新选择最小边后重新选择最小边 closedgej=G.vexsk，G.arcskj.adj； /MiniSpanTree7.4 7.4 图的连通性图的连通性算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法） 为使生成树上边的权值之和最小，显然，其为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔中每一条边的权值应该尽可能地小。克

52、鲁斯卡尔算法的做法就是：先构造一个只含算法的做法就是：先构造一个只含n个顶点的子个顶点的子图图SG，然后从权值最小的边开始，若它的添加不，然后从权值最小的边开始，若它的添加不使使SG中产生回路，则在中产生回路，则在SG上加上这条边，如此上加上这条边，如此重复，直至加上重复，直至加上n-1条边为止。条边为止。7.4 7.4 图的连通性图的连通性克鲁斯卡尔算法构造最小生成树的过程v2v4v6v3v1v5v1v4v6v5v2v3651534626(a)1425357.4 7.4 图的连通性图的连通性一般来讲，一般来讲， 由于由于普里姆算法的时间复杂度为普里姆算法的时间复杂度为O(n2)，则适于稠密图

53、；而克鲁斯卡尔算法需对则适于稠密图；而克鲁斯卡尔算法需对e条边条边按权值进行排序，其时间复杂度为按权值进行排序，其时间复杂度为O(eloge)，则适于稀疏图。则适于稀疏图。7.4 7.4 图的连通性图的连通性7.4 7.4 图的连通性图的连通性 “最小生成树最小生成树”主要是针对主要是针对“无向图无向图”而言的，请思考它主而言的，请思考它主要能解决哪些实际生活中遇到的要能解决哪些实际生活中遇到的问题？问题？第 61 页7.6 7.6 最短路径最短路径7.6.1 7.6.1 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径问题提出用带权的有向图表示一个交通运输网，图中：用带权的有

54、向图表示一个交通运输网，图中：顶点顶点表示城市表示城市边边表示城市间的交通联系表示城市间的交通联系权权表示此线路的长度或沿此线路运输所花的时间或费表示此线路的长度或沿此线路运输所花的时间或费用等用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径径中，各边上权值之和最小的一条路径最短路径最短路径 第 62 页7.6 7.6 最短路径最短路径7.6.1 7.6.1 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径l给定带权有向图给定带权有向图G G和源点和源点v,v,求从求从v v到到G G中其

55、余各顶点的中其余各顶点的最短路径最短路径l例例: :求求v v0 0到其余顶点的最短路径到其余顶点的最短路径V1V5V2V4V0V35501001060201030始点 终点 最短路径 路径长度 v0 v1 无 v2 (v0,v2) 10 v3 (v0,v4,v3) 50 v4 (v0,v4) 30 v5 (v0,v4,v3,v5) 60第 63 页迪杰斯特拉迪杰斯特拉(Dijkstra)(Dijkstra)算法算法l(1)(1)设置两个顶点的集合设置两个顶点的集合T T和和S;S;集合集合S S存放已找到最短路径的顶点存放已找到最短路径的顶点集合集合T T存放当前还未找到最短路径的顶点存放当

56、前还未找到最短路径的顶点l(2)(2)初始状态时初始状态时,S,S只包含源点只包含源点v v0 0 ; ;l(3)(3)从从T T中选取某个顶点中选取某个顶点v vi i( (要求要求v vi i 到到v v0 0的路径长度最短的路径长度最短) ) 加入到加入到S S中中,;,;l(4)S(4)S中每加入一个顶点中每加入一个顶点v vi i, ,都要修改顶点都要修改顶点v v0 0到到T T中剩余顶点的最短中剩余顶点的最短路径长度值路径长度值; ;它们的值为原来值与新值的较小者它们的值为原来值与新值的较小者; ;新值是新值是v vi i的最短路径长度值加上的最短路径长度值加上v vi i到该顶

57、点的路径长到该顶点的路径长度度l(5)(5)不断重复不断重复(3)(3)和和(4),(4),直到直到S S包含全部顶点包含全部顶点; ;第 64 页V1V5V2V4V0V35501001060201030迪杰斯特拉(Dijkstra)算法举例带权邻接矩阵为: 10 30 100 5 50 10 20 60 第 65 页最短路径的求解过程最短路径的求解过程 终点 v1 v2 v3 v4 v5 vi步骤1 10 30 100 v2 (v0,v2) (v0,v4) (v0,v5)步骤2 60 30 100 v4 (v0,v2,v3) (v0,v4) (v0,v5)步骤3 50 90 v3 (v0,v

58、4,v3) (v0,v4,v5)步骤4 60 v5 (v0,v4,v3,v5)步骤5 无第 66 页7.6 7.6 最短路径最短路径7.6.2 7.6.2 每一对顶点间的最短路径每一对顶点间的最短路径l给定带权有向图给定带权有向图G,G,求求G G中每个顶点到其余各顶点的最中每个顶点到其余各顶点的最短路径短路径l例例: :求有向网求有向网G G的每一对顶点的最短路径的每一对顶点的最短路径V0V2V1624113有向网G0 4 116 0 23 0邻接矩阵第 67 页FloydFloyd算法算法l(1)(1)递推产生一个矩阵序列递推产生一个矩阵序列A A0 0,A,A1 1,.,A,.,Ak k

59、,.A,.An n 其中其中A Ak ki,ji,j表示从顶点表示从顶点v vi i到到v vj j的路径上所经过的的路径上所经过的顶点序号不大于顶点序号不大于k k的最短路径长度的最短路径长度l(2)(2)初始时初始时, A, A0 0为邻接矩阵为邻接矩阵. .l(3)A(3)Ak+1k+1i,j=minAi,j=minAk ki,j, Ai,j, Ak ki,k+1+Ai,k+1+Ak kk+1,jk+1,j (0=k=n-1) (0=k=n-1)0 4 116 0 23 0A0=0 4 65 0 23 7 0A2=0 4 66 0 23 0A1=第 68 页例ACB2643110 4 116 0 23 0初始：路径：