数据结构第6章图

1、 2022年6月27日 2022年6月27日 线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树集合数据元素间除“同属于一个集合”外，无其它关系图形结构多个对多个，如图逻辑结构逻辑结构 2022年6月27日 第第6 6章图章图6.16.1图的定义和基本术语图的定义和基本术语6.26.2图的存储结构图的存储结构6.36.3图的遍历图的遍历6.46.4图的应用图的应用教学内容教学内容 2022年6月27日 1.1.掌握：图的基本掌握：图的基本概念及相关术语和性质概念及相关术语和性质2.2.熟练掌握：图的熟练掌握：图的邻接矩阵和邻接表邻接矩阵和邻接表两种存储表示方法两种存储表示方法3.3

2、.熟练掌握：图的两种遍历方法熟练掌握：图的两种遍历方法DFSDFS和和BFSBFS4.4.熟练掌握：最短路算法（熟练掌握：最短路算法（DijkstraDijkstra算法算法）5.5.掌握：掌握：最小生成树最小生成树的两种算法及的两种算法及拓扑排序拓扑排序算法的思想算法的思想教学目标教学目标 2022年6月27日 6.1 6.1 图的定义和术语图的定义和术语V1V2V3V4G1V1V2V4V5G2V3图：图：Graph=(V,E) V：顶点：顶点(数据元素数据元素)的的有穷非空有穷非空集合；集合； E：边的：边的有穷有穷集合。集合。无向图：无向图：有向图：有向图：每条边都是无方向的每条边都是无

3、方向的每条边都是有方向的每条边都是有方向的 2022年6月27日 完全图：完全图：任意两个点都有一条边相连任意两个点都有一条边相连无向完全图无向完全图有向完全图有向完全图 2022年6月27日 稀疏图稀疏图：有很少边或弧的图。：有很少边或弧的图。稠密图稠密图：有较多边或弧的图。：有较多边或弧的图。网网：边：边/弧带权的图。弧带权的图。邻接邻接：有边：有边/弧相连的两个顶点之间的关系。弧相连的两个顶点之间的关系。 存在存在(vi, vj)，则称，则称vi和和vj互为互为邻接点邻接点； 存在存在，则称，则称vi邻接到邻接到vj， vj邻接于邻接于vi 关联关联(依附依附)：边边/弧与顶点之间的关系

4、。弧与顶点之间的关系。 存在存在(vi, vj)/ ， 则称该边则称该边/弧关联于弧关联于vi和和vj 2022年6月27日 顶点的度顶点的度：与该顶点相关联的边的数目，记为：与该顶点相关联的边的数目，记为TD(v)在在有向图有向图中中, 顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数, 记作记作 ID(v) 顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条数为始点的有向边的条数, 记作记作OD(v)问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其其余

5、顶点的入度均为余顶点的入度均为1 1，此时是何形状？，此时是何形状？答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！ 2022年6月27日 路径路径：接续的边构成的顶点序列。：接续的边构成的顶点序列。路径长度路径长度：路径上边或弧的数目：路径上边或弧的数目/权值之和。权值之和。回路回路(环环)：第一个顶点和最后一个顶点相同的路径。第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：除路径起点和终点可以相同外，其余顶点均不相同除路径起点和终点可以相同外，其余顶点均不相同的路径。的路径。简单回路简单回路(简单环简单环)：除路径起点和终点相同外，其余顶点均不除路径起点和终点相同外，其余顶

6、点均不相同的路径。相同的路径。 2022年6月27日 非连通图非连通图 连通图连通图 强连通图强连通图 非强连通图非强连通图 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4在无（有）向图在无（有）向图G=( V, E )G=( V, E )中，若对任何两个顶中，若对任何两个顶点点 v v、u u 都存在从都存在从v v 到到 u u 的路径，则称的路径，则称G G是连通图是连通图（强连通图）。（强连通图）。 2022年6月27日 (a)(a)(b)(b)

7、(c)(c) V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2设有两个图设有两个图G=G=（V V，EE）、）、G1=G1=（V1V1，E1E1），），若若V1V1 V V，E1 E1 E E，则称，则称 G1G1是是G G的子图。的子图。例例:(b):(b)、(c) (c) 是是 (a) (a) 的子图的子图图中边或弧所具有的相关数称为权。表明从一个顶图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。点到另一个顶点的距离或耗费。带权的图称为带权的图称为。 2022年6月2

8、7日 非连通图非连通图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4无向图无向图G G 的极大连通子图称为的极大连通子图称为G G的连通分量。的连通分量。极大连通子图意思是：该子图是极大连通子图意思是：该子图是 G G 连通子图，将连通子图，将G G 的任何不在该子图中的顶点加入，子图不再连通。的任何不在该子图中的顶点加入，子图不再连通。 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4连通分量连通分量 2022年6月27日 有向图有向图G G 的极大强连通子图称为的极大强连通子图称为G G的强连通分量。的强连通分量。极大强连通子图意思是：该子图是极大强连通子图意思是：

9、该子图是G G的强连通子图的强连通子图，将，将D D的任何不在该子图中的顶点加入，子图不再的任何不在该子图中的顶点加入，子图不再是强连通的。是强连通的。强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 2022年6月27日 ：该子图是：该子图是G G 的连通子图，在该子图的连通子图，在该子图中删除任何一条边，子图不再连通。中删除任何一条边，子图不再连通。包含无向图包含无向图G G 所有顶点的极小连通子图。所有顶点的极小连通子图。对非连通图，由各个连通分量的生成树对非连通图，由各个连通分量的生成树的集合。的集合。 连通图连通图 G1G1G1G1

10、的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 2022年6月27日 6.2 6.2 图的存储结构图的存储结构邻接表邻接表邻接多重表邻接多重表十字链表十字链表链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：数组表示法（邻接矩阵）数组表示法（邻接矩阵）多重链表多重链表重点介绍：重点介绍： 2022年6月27日 , ),( , , .否否则则或或者者如如果果01AEjiEjijiEdgev建立一个建立一个顶点表顶点表（记录各个顶点信息）（记录各个顶点信息）和一个和一个邻接

11、矩邻接矩阵阵（表示各个顶点之间关系）（表示各个顶点之间关系）。v设图设图 A = (A = (V V, , E E) ) 有有 n n 个顶点，则图的邻接矩阵是个顶点，则图的邻接矩阵是一个二维数组一个二维数组 A.EdgennA.Edgenn，定义为：，定义为：数组（邻接矩阵）表示法数组（邻接矩阵）表示法 2022年6月27日 邻接矩阵：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的；分析分析2 2：顶点顶点i i

12、 的的度度第第 i i 行行 ( (列列) ) 中中1 1 的个数的个数；特别：特别：完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余，其余1 1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：无向图的邻接矩阵表示法无向图的邻接矩阵表示法v1v2v3v5v4v4 2022年6月27日 有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。顶点的顶点的出度出度= =第第i i行元素之和行元素之和 顶点的顶点的入度入度= =

13、第第i i列元素之和列元素之和 顶点的顶点的度度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和 v1v2v3v4邻接矩阵：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧( (即出度边）；即出度边）； 第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧( (即入度边）。即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1

14、 00 0 0 0 0 0 0 1 1 0 0 0 有向图的邻接矩阵表示法有向图的邻接矩阵表示法 2022年6月27日 定义为：定义为： A.Edge i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613邻接矩阵： N.Edge =( v1 v2 v3 v4 v5 v6 )顶点表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 网（即有权图）的邻接矩阵表示法网（即有权图）的邻接矩阵表示法 2022年6月27日 优点：优点：容易实现图的操作，如：求某顶点的度、判容易实现图的操作，如：求某顶点的度、判断顶

15、点之间是否有边、找顶点的邻接点等等。断顶点之间是否有边、找顶点的邻接点等等。缺点：缺点：n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边; ;空间效率为空间效率为O(nO(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵表示法的特点邻接矩阵表示法的特点 2022年6月27日 /用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define MaxInt 32767 /表示极大值，即表示极大值，即#define MVNum 100 /最大顶点数最大顶点数 typedef char VerTexType; /假设顶点的数据类型为

16、字符型假设顶点的数据类型为字符型 typedef int ArcType; /假设边的权值类型为整型假设边的权值类型为整型 typedef struct VerTexType vexsMVNum; /顶点表顶点表 ArcType arcsMVNumMVNum; /邻接矩阵邻接矩阵 int vexnum,arcnum; /图的当前点数和边数图的当前点数和边数 AMGraph; 邻接矩阵的存储表示邻接矩阵的存储表示 2022年6月27日 （1 1）输入）输入总顶点数和总边数总顶点数和总边数。（2 2）依次输入）依次输入点的信息存入顶点表点的信息存入顶点表中。中。（3 3）初始化邻接矩阵初始化邻接矩

17、阵，使每个权值初始化为极大值。，使每个权值初始化为极大值。（4 4）构造邻接矩阵构造邻接矩阵。 【算法思想算法思想】采用邻接矩阵表示法创建无向网采用邻接矩阵表示法创建无向网 2022年6月27日 Status CreateUDN(AMGraph &G) /采用邻接矩阵表示法，创建无向网采用邻接矩阵表示法，创建无向网G cinG.vexnumG.arcnum; /输入总顶点数，总边数输入总顶点数，总边数 for(i = 0; iG.vexsi; /依次输入点的信息依次输入点的信息 for(i = 0; iG.vexnum;+i) /初始化邻接矩阵，边的权值均置为极大值初始化邻接矩阵，边的权值均置

18、为极大值 for(j = 0; jG.vexnum;+j) G.arcsij = MaxInt; for(k = 0; kv1v2w; /输入一条边依附的顶点及权值输入一条边依附的顶点及权值 i = LocateVex(G, v1); j = LocateVex(G, v2); /确定确定v1和和v2在在G中的位置中的位置 G.arcsij = w; /边边的权值置为的权值置为w G.arcsji = G.arcsij; /置置的对称边的对称边的权值为的权值为w /for return OK; /CreateUDN 【算法描述算法描述】 2022年6月27日 int LocateVex(MGr

19、aph G,VertexType u) /* 初始条件初始条件:图图G存在存在,u和和G中顶点有相同特征中顶点有相同特征 */ /* 操作结果操作结果:若若G中存在顶点中存在顶点u,则返回该顶点在图中则返回该顶点在图中位置位置;否则返回否则返回-1 */ int i; for(i=0;iG.vexnum;+i) if(u=G.vexsi) return i; return -1; 2022年6月27日 v 对每个顶点对每个顶点vi 建立一个建立一个单链表单链表，把与，把与vi有关联的有关联的边的信息链接边的信息链接起来，每个结点设为起来，每个结点设为3个域；个域；adjvex nextarci

20、nfodatafirstarc邻接点域邻接点域，表表示示vi一个邻接一个邻接点的位置点的位置链域链域，指向指向vi下一个边下一个边或弧的结点或弧的结点数据域数据域，与与边有关信息边有关信息（如权值）（如权值）数据域数据域，存存储顶点储顶点vi 信信息息链域链域，指向，指向单链表的第单链表的第一个结点一个结点邻接表（链式）表示法邻接表（链式）表示法 2022年6月27日 0123413341420注：注：邻接表不唯一邻接表不唯一，因各个边结点的链入顺序是任意的，因各个边结点的链入顺序是任意的v1v2v3v4v5231420无向图的邻接表表示无向图的邻接表表示空间效率为空间效率为O(n+2e)O(

21、n+2e)。若是稀疏图若是稀疏图(en(eG.vexnumG.arcnum; /输入总顶点数，总边数输入总顶点数，总边数 for(i = 0; i G.verticesi.data; /输入顶点值输入顶点值 G.verticesi.firstarc=NULL; /初始化表头结点的指针域为初始化表头结点的指针域为NULL /for for(k = 0; kv1v2; /输入一条边依附的两个顶点输入一条边依附的两个顶点 i = LocateVex(G, v1); j = LocateVex(G, v2); p1=new ArcNode; /生成一个新的边结点生成一个新的边结点*p1 p1-adjv

22、ex=j; /邻接点序号为邻接点序号为j p1-nextarc= G.verticesi.firstarc; G.verticesi.firstarc=p1; /将新结点将新结点*p1插入顶点插入顶点vi的边表头部的边表头部 p2=new ArcNode; /生成另一个对称的新的边结点生成另一个对称的新的边结点*p2 p2-adjvex=i; /邻接点序号为邻接点序号为i p2-nextarc= G.verticesj.firstarc; G.verticesj.firstarc=p2; /将新结点将新结点*p2插入顶点插入顶点vj的边表头部的边表头部 /for return OK; /Cre

23、ateUDG 【算法描述算法描述】 2022年6月27日 优点：优点：空间效率高，容易寻找顶点的邻接点；空间效率高，容易寻找顶点的邻接点；缺点：缺点：判断两顶点间是否有边或弧，需搜索两结判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。点对应的单链表，没有邻接矩阵方便。邻接表表示法的特点邻接表表示法的特点 2022年6月27日 v1v2v3v5v4v44321013341420v5v4v3v2v1231420（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01

24、0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。 2022年6月27日 2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是对于任一确定的无向图，邻接矩阵是唯一唯一的（行列的（行列号与顶点编号一致），但邻接表号与顶点编号一致），但邻接表不唯一不

25、唯一（链接次序（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵多用于邻接矩阵多用于稠密图稠密图；而邻接表多用于；而邻接表多用于稀稀疏图疏图邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系 2022年6月27日 遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做问一次，就叫做图的图

26、的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且图的任一顶点都可，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边会沿着某些边又回到了曾经访问过的顶点又回到了曾经访问过的顶点6.3 6.3 图的遍历图的遍历 2022年6月27日 图常用的遍历：图常用的遍历：深度优先搜索深度优先搜索广度优先搜索广度优先搜索解决思路：解决思路：设置设置辅助数组辅助数组 visitedvisited n n ，用来标记每，用来标记每个被访问过的顶点。个

27、被访问过的顶点。初始状态为初始状态为0 0i i 被访问，改被访问，改 visitedvisited i i 为为1 1，防止被多次访问，防止被多次访问怎样避免重复访问？怎样避免重复访问？ 2022年6月27日 基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。v1v2v3v8v7v6v4v5起点起点深度优先搜索深度优先搜索( DFS ( DFS Depth_First Search)Depth_First Search) 2022年6月27日 深度优先搜索的步骤深度优先搜索的步骤简单归纳：简单归纳：访问起访问起始点始点v v; ;若若v v的的第第1 1个个邻接点没访问过，邻接点没

28、访问过，深度遍历深度遍历此邻接此邻接点；点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v v的第的第2 2个邻接点个邻接点重新遍历。重新遍历。 2022年6月27日 深度优先搜索的步骤深度优先搜索的步骤详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点 v 后，后，由由 v 出发，访问出发，访问它的任一邻接顶它的任一邻接顶点点 w1；E再从再从 w1 出发，访问出发，访问与与 w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点 w2；E然后再从然后再从 w2 出发，进行类似的出发，进行类似的访问，访问， E如此进行下去，直至到达所有如此进行下去，直至到达所有的邻接顶

29、点都被访问过的顶点的邻接顶点都被访问过的顶点 u 为止。为止。起点起点 2022年6月27日 深度优先搜索的步骤深度优先搜索的步骤详细归纳：详细归纳：E接着，退回一步，接着，退回一步，退到前一次退到前一次刚访问过的顶点刚访问过的顶点，看是否还有其，看是否还有其它没有被访问的邻接顶点。它没有被访问的邻接顶点。 如果有，如果有，则访问此顶点，之后则访问此顶点，之后再从此顶点出发，进行与前述类再从此顶点出发，进行与前述类似的访问；似的访问； 如果没有，如果没有，就就再退回一步再退回一步进行进行搜索。重复上述过程，直到连通搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。图中所有顶点都被访问过为

30、止。起点起点 2022年6月27日 讨论讨论1 1：计算机如何实现：计算机如何实现DFSDFS？1 2345610 000000 0000030 0000040 0000050 0000060 00000000000123456010000100001000010101邻邻接接矩矩阵阵A辅助数组辅助数组 visited n 起点起点开辅助数组开辅助数组 visited n ！1 23 456100000 00300 00400 005000060 0000 2022年6月27日 void DFS(AMGraph G, int v) /图图G为邻接矩阵类型为邻接矩阵类型 coutv; visit

31、edv = true; /访问第访问第v个顶点个顶点 for(w = 0; w G.vexnum; w+) /依次检查邻接矩阵依次检查邻接矩阵v所在的行所在的行 if(G.arcsvw!=0)& (!visitedw) DFS(G, w); /w是是v的邻接点，如果的邻接点，如果w未访问，则递归调用未访问，则递归调用DFS 可以用递归算法！可以用递归算法！ 2022年6月27日 00000123辅助数组辅助数组 visited n 1000110011101111照样借用照样借用visited n ！起点起点0123 2022年6月27日 void DFS(ALGraph G, int v)

32、/图图G为邻接表类型为邻接表类型 coutadjvex; /表示表示w是是v的邻接点的邻接点 if(!visitedw) DFS(G, w); /如果如果w未访问，则递归调用未访问，则递归调用DFS p=p-nextarc; /p指向下一个边结点指向下一个边结点 仍可用递归算法仍可用递归算法 2022年6月27日 n用用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点都要来表示图，遍历图中每一个顶点都要从头扫描从头扫描该顶点所在行，时间复杂度为该顶点所在行，时间复杂度为O(O(n n2 2) )。n用用邻接表邻接表来表示图，虽然有来表示图，虽然有 2 2e e 个表结点，但只个表结点，但只需扫描需

33、扫描 e e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n n个个头结点的时间，时间复杂度为头结点的时间，时间复杂度为O(O(n n+ +e e) )。结论：结论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。DFSDFS算法效率分析算法效率分析 2022年6月27日 基本思想：基本思想：仿树的层次遍历过程仿树的层次遍历过程广度优先搜索广度优先搜索( BFS ( BFS Breadth_First Search)Breadth_First Search)v1v2v3v8v7v6v4v5

34、起点起点 2022年6月27日 简单归纳：简单归纳：在访问了在访问了起始点起始点v v之后，依次访问之后，依次访问 v v的邻接点的邻接点；然后再依次访问然后再依次访问这些顶点中未被访问过的邻接点这些顶点中未被访问过的邻接点；直到所有顶点都被访问直到所有顶点都被访问过为止。过为止。广度优先搜索是一种广度优先搜索是一种分层分层的搜索过程，每向前的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。那样有回退的情况。因此，广度优先搜索因此，广度优先搜索不是一个递归不是一个递归的过程，其的过程，其算法也不是递归的。算法也不是递归的。广度优

35、先搜索的步骤广度优先搜索的步骤 2022年6月27日 讨论讨论1 1：计算机如何实现：计算机如何实现BFSBFS？邻接表邻接表除辅助数组除辅助数组visited n 外，外，还需再开一辅助队列还需再开一辅助队列起点起点辅助队列辅助队列v2已访问过了已访问过了BFS BFS 遍历结果遍历结果入队！入队！初始初始f=n-1,r=0f=n-1,r=0 2022年6月27日 （1 1）从图中某个顶点）从图中某个顶点v v出发，访问出发，访问v v，并置，并置visitedvisitedv v 的值为的值为truetrue，然后将，然后将v v进队。进队。（2 2）只要队列不空，则重复下述处理。）只要队

36、列不空，则重复下述处理。 队头顶点队头顶点u u出队。出队。 依次检查依次检查u u的所有邻接点的所有邻接点w w，如果，如果visitedvisitedw w 的值为的值为falsefalse，则访问，则访问w w，并置，并置visitedvisitedw w 的值为的值为truetrue，然后将，然后将w w进队。进队。【算法思想算法思想】 2022年6月27日 void BFS (Graph G, int v) /按广度优先非递归遍历连通图按广度优先非递归遍历连通图G cout=0; w = NextAdjVex(G, u, w) if(!visitedw) /w为为u的尚未访问的邻接顶

37、点的尚未访问的邻接顶点 coutw; visitedw = true;EnQueue(Q, w); /w进队进队 /if /while /BFS 【算法描述算法描述】 2022年6月27日 如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（，都要循环检测矩阵中的整整一行（ n 个元素），总个元素），总的时间代价为的时间代价为O(n2)。 用邻接表来表示图，虽然有用邻接表来表示图，虽然有 2e 个表结点，但只需扫描个表结点，但只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个头结点的时间，个头结

38、点的时间，时间复杂度为时间复杂度为O(n+e)。BFSBFS算法效率分析算法效率分析 2022年6月27日 空间复杂度相同，都是空间复杂度相同，都是O(n)O(n)( (借用了堆栈或队列）；借用了堆栈或队列）； 时间复杂度只与存储结构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有关，有关，而与搜索路径无关。而与搜索路径无关。DFSDFS与与BFSBFS算法效率比较算法效率比较 2022年6月27日 最小生成树最小生成树最短路径最短路径拓扑排序拓扑排序关键路径关键路径6.4 6.4 图的应用图的应用 2022年6月27日 ：该子图是该子图是G G 的连通子图，在该子图中删的连通

39、子图，在该子图中删除任何一条边，子图不再连通。除任何一条边，子图不再连通。包含图包含图G G所有顶点的极小连通子图（所有顶点的极小连通子图（n-1条边）条边）。G1G1的生成树的生成树连通图连通图 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小生成树最小生成树 2022年6月27日 DFSDFS生生成成树树邻邻接接表表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFSBFS生生成成树树v0v1v3v2v4无向连通图无向连通图画出下图的生成树画出下

40、图的生成树v0v1v2v4v4v3 2022年6月27日 求最小生成树求最小生成树首先明确首先明确： 使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树 从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树的生成树有有 n n 个顶点、个顶点、n-n-1 1 条边。条边。目标：目标：在网的多个生成树中，寻找一个在网的多个生成树中，寻找一个各边各边权值之和最小权值之和最小的生成树的生成树 2022年6月27日 v必须只使用该必须只使用该网中的

41、边网中的边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n-1n-1条边条边来联结网络中的来联结网络中的n n个个顶点顶点v不能使用产生不能使用产生回路回路的边的边构造最小生成树的准则构造最小生成树的准则 2022年6月27日 欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条条线路；但因为每条线路都会有对应的经济成本，而线路；但因为每条线路都会有对应的经济成本，而n n个个城市可能有城市可能有n(n-1)/2 n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条条线路，使总费用最少？线路，使总费用

42、最少？数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n n1 1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显然此连通网显然此连通网是一个是一个生成树生成树！最小生成树的典型用途最小生成树的典型用途 2022年6月27日 v PrimPrim（普里姆）算法（普里姆）算法 v KruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法PrimePrime算法算法: : 归并顶点归并顶点，与边数无关，适于，与边数无关，适于稠密网稠密网Kruskal算法：算法：归并边归

43、并边，适于，适于稀疏网稀疏网如何求最小生成树如何求最小生成树 2022年6月27日 设连通网络设连通网络 N = V, E 生成树的顶点集合生成树的顶点集合UU普里姆算法的基本思想普里姆算法的基本思想归并顶点归并顶点 2022年6月27日 应用普里姆算法构造最小生成树的过程应用普里姆算法构造最小生成树的过程 2022年6月27日 设连通网络设连通网络 N = V, E 1. 构造一个只有构造一个只有 n 个顶点，没有边的非连通图个顶点，没有边的非连通图 T = V, , 每个顶点自成一个连通分量每个顶点自成一个连通分量 2. 在在 E 中选最小权值的边中选最小权值的边,若该边的两个顶点落若该边

44、的两个顶点落在不同的连通分量上，则加入在不同的连通分量上，则加入 T 中；否则舍去中；否则舍去，重新选择，重新选择 3. 重复下去，直到所有顶点在同一连通分量上重复下去，直到所有顶点在同一连通分量上为止为止克鲁斯卡尔算法的基本思想克鲁斯卡尔算法的基本思想归并边归并边 2022年6月27日 应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程 2022年6月27日 用有向图来描述一个工程或系统的进行过程。用有向图来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只要完成了这些子工程一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的

45、完成。（活动），就可以导致整个工程的完成。 AOVAOV网网(Activity On Vertices)(Activity On Vertices)用用顶点顶点表示活动的网络表示活动的网络 AOEAOE网网(Activity On Edges)(Activity On Edges)用用边边表示活动的网络表示活动的网络比如教学计划的制定比如教学计划的制定哪些课程是必须先修的，哪些课程是可以并行学习的。哪些课程是必须先修的，哪些课程是可以并行学习的。有向无环图及其应用有向无环图及其应用 2022年6月27日 2022年6月27日 学生课程学习工程图学生课程学习工程图 对学生选课工程图进行拓扑排序，

46、得到的拓扑有序序列为对学生选课工程图进行拓扑排序，得到的拓扑有序序列为C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 2022年6月27日 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。 在在AOV网络中网络中选一个没有直接前驱的顶点选一个没有直接前驱的顶点, 并输出之并输出之; 从图中删去该顶点从图中删去该顶点, 同时删去所有它发出的有向边同时删去所有它发出的有向边; 重复以上重复以上 2、3 步步, 直到：直到：u全部顶点均已输出，拓扑有序序列形成，

47、拓扑排序全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或：完成；或：u图中还有未输出的顶点，但已跳出处理循环。这说图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时找不到没有前驱的顶点了。这时AOV网络中必定存网络中必定存在有向环。在有向环。拓扑排序算法的思想拓扑排序算法的思想重复选择没有直接前驱的顶点重复选择没有直接前驱的顶点 2022年6月27日 拓扑排序的过程拓扑排序的过程 2022年6月27日 2022年6月27日 典型用途：典型用途：交通问题。如：城市交通问题。如：城市A

48、 A到城市到城市B B有多条线路，有多条线路，但每条线路的交通费（或所需时间）不同，那么，但每条线路的交通费（或所需时间）不同，那么，如何如何选择一条线路，使总费用（或总时间）最少？选择一条线路，使总费用（或总时间）最少？问题抽象：问题抽象：在在带权有向图带权有向图中中A A点（源点）到达点（源点）到达B B点（终点）点（终点）的多条路径中，寻找一条的多条路径中，寻找一条各边权值之和最小各边权值之和最小的路径，即的路径，即最短路径。最短路径。（注：最短路径与最小生成树不同，路径上（注：最短路径与最小生成树不同，路径上不一定包含不一定包含n n个顶点）个顶点）最短路径最短路径 2022年6月27

49、日 一顶点到其一顶点到其余各顶点余各顶点两种常见的最短路径问题：两种常见的最短路径问题：一、一、 单源最短路径单源最短路径用用Dijkstra（迪杰斯特拉）（迪杰斯特拉）算法算法二、所有顶点间的最短路径二、所有顶点间的最短路径用用Floyd（弗洛伊德）算法（弗洛伊德）算法任意两顶任意两顶点之间点之间 2022年6月27日 目的：目的： 设一设一有向图有向图G=G=（V, EV, E），已知各边的权值，以某），已知各边的权值，以某指定点指定点v v0 0为源点，求从为源点，求从v v0 0到图的其余各点的最短路径。到图的其余各点的最短路径。限定限定各边上的权值大于或等于各边上的权值大于或等于0

50、0。源点源点从从FAFA的路径有的路径有4 4条：条： FAFA： 2424 FBA FBA： 5 518=2318=23 FBCA FBCA：5+7+9=215+7+9=21 FDCAFDCA：25+12+9=3625+12+9=36又：又：从从FBFB的最短路径是哪条？的最短路径是哪条？从从FCFC的最短路径是哪条？的最短路径是哪条？单源最短路径问题（单源最短路径问题（DijkstraDijkstra算法）算法） 2022年6月27日 v0(v0, v1)10源点源点终点终点 最最 短短路路 径径路径长度路径长度(v0, v1, v2) (v0, v3, v2)(v0, v3)30 v1

51、v2 v3 v4100(v0, v4)(v0, v3, v4)(v0, v3, v2, v4) 6001234 5090 70讨论：计算机如何自动求出这些最短路径？讨论：计算机如何自动求出这些最短路径？(v0, v1, v2, v4)60 2022年6月27日 先找出从源点先找出从源点v v0 0到各终点到各终点v vk k的直达路径（的直达路径（v v0 0,v,vk k），即），即通过一条弧到达的路径。通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（从这些路径中找出一条长度最短的路径（v v0 0,u,u）, ,然后然后对其余各条路径进行适当调整：对其余各条路径进行适当调整：若在

52、图中存在弧（若在图中存在弧（u,vu,vk k），且（），且（v v0 0,u,u）+ +（u,vu,vk k） （v v0 0,v,vk k）, ,则以路径（则以路径（v v0 0,u,v,u,vk k）代替（）代替（v v0 0,v,vk k）。）。在调整后的各条路径中，再找长度最短的路径，依此在调整后的各条路径中，再找长度最短的路径，依此类推。类推。DijkstraDijkstra算法的思想算法的思想 2022年6月27日 初始化：初始化：将源点将源点v0加到加到S中，即中，即Sv0 = true；将将v0到各个终点的最短路径长度初始化为权值，到各个终点的最短路径长度初始化为权值，即即D

53、i = G.arcsv0vi，(viV S)；如果如果v0和顶点和顶点vi之间有弧，则将之间有弧，则将vi的前驱置为的前驱置为v0，即即Pathi = v0，否则，否则Pathi = 1。 选择下一条最短路径的终点选择下一条最短路径的终点vk，使得：，使得：Dk = MinDi|viV S【算法思想算法思想】 2022年6月27日 将将vk加到加到S中，即中，即Svk = true。 更新从更新从v0出发到集合出发到集合V S上任一顶点的最短路径的上任一顶点的最短路径的长度，同时更改长度，同时更改vi的前驱为的前驱为vk。若若Dk+G.arcskiDi，则，则Di=Dk+ G.arcski; Path i=k;。 重复重复 n 1次，即可按照路径长度的递增顺序次，即可按照路径长度的递增顺序，逐个求得从，逐个求得从v0到图上其余各顶点的最短路径。到图上其余各顶点的最短路径。【算法思想算法思想】 2022年6月27日 初始化各类结构（辅助结构）依次求V o 到V i的最短距离i= 1i n找V j, D j = m in D j V j加入S 中修改其它顶点的最短路径i+ +结束 2022年6月27日 (v0,v2)+ (v2,v3)(v0,v3)终终点点 从从v0到各终点的到各终点的di