第6章-图(学生)课件

2024年7月14日 数据结构数据结构 2024年7月14日 第第6 6章图章图6.16.1图的定义和基本术语图的定义和基本术语6.26.2图的存储结构图的存储结构6.36.3图的遍历图的遍历6.46.4图的应用图的应用教学内容教学内容 2024年7月14日 1.1.掌握：图的基本掌握：图的基本概念及相关术语和性质概念及相关术语和性质2.2.熟练掌握：图的熟练掌握：图的邻接矩阵和邻接表邻接矩阵和邻接表两种存储表示方法两种存储表示方法3.3.熟练掌握：图的两种遍历方法熟练掌握：图的两种遍历方法DFSDFS和和BFSBFS4.4.熟练掌握：最短路算法（熟练掌握：最短路算法（DijkstraDijkstra算法算法）5.5.掌握：掌握：最小生成树最小生成树的两种算法及的两种算法及拓扑排序拓扑排序算法的思想算法的思想教学目标教学目标 2024年7月14日 6.1 6.1 图的定义和术语图的定义和术语图：图：Graph=(V,E)V：顶点：顶点(数据元素数据元素)的的有穷非空有穷非空集合；集合；E：边的：边的有穷有穷集合。集合。无向图：无向图：有向图：有向图：每条边都是无方向的每条边都是无方向的每条边都是有方向的每条边都是有方向的 2024年7月14日 完全图：完全图：任意两个点都有一条边相连任意两个点都有一条边相连无向完全图无向完全图有向完全图有向完全图n n(n n-1)/2-1)/2条边条边条边条边n n(n n-1)-1)条边条边条边条边 2024年7月14日 稀疏图稀疏图：有很少边或弧的图。：有很少边或弧的图。稠密图稠密图：有较多边或弧的图。：有较多边或弧的图。网网：边：边/弧带权的图。弧带权的图。邻接邻接：有边：有边/弧相连的两个顶点之间的关系。弧相连的两个顶点之间的关系。存在存在(vi,vj)，则称，则称vi和和vj互为互为邻接点邻接点；存在存在，则称，则称vi邻接到邻接到vj，vj邻接于邻接于vi 关联关联(依附依附)：边边/弧与顶点之间的关系。弧与顶点之间的关系。存在存在(vi,vj)/，则称该边则称该边/弧关联于弧关联于vi和和vj 2024年7月14日 顶点的度顶点的度：与该顶点相关联的边的数目，记为：与该顶点相关联的边的数目，记为TD(v)在在有向图有向图中中,顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。顶点顶点v的入度的入度是以是以v为终点的有向边的条数为终点的有向边的条数,记作记作ID(v)顶点顶点v的出度的出度是以是以v为始点的有向边的条数为始点的有向边的条数,记作记作OD(v)问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余其余顶点的入度均为顶点的入度均为1 1，此时是何形状？，此时是何形状？（经验值（经验值200200）答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！2024年7月14日 路径路径：接续的边构成的顶点序列。：接续的边构成的顶点序列。路径长度路径长度：路径上边或弧的数目：路径上边或弧的数目/权值之和。权值之和。回路回路(环环)：第一个顶点和最后一个顶点相同的路径。第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：除路径起点和终点可以相同外，其余顶点均不相同除路径起点和终点可以相同外，其余顶点均不相同的路径。的路径。简单回路简单回路(简单环简单环)：除路径起点和终点相同外，其余顶点均不除路径起点和终点相同外，其余顶点均不相同的路径。相同的路径。2024年7月14日 非非连连通通图图 连连通通图图 强强连连通通图图 非非强强连连通通图图 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是连通图是连通图（强连通图）。（强连通图）。2024年7月14日 (a)(a)(b)(b)(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)的子图的子图权与网权与网权与网权与网图中边或弧所具有的相关数称为权。表明从一个顶图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。点到另一个顶点的距离或耗费。带权的图称为带权的图称为网网网网。2024年7月14日 连通分量（强连通分量）连通分量（强连通分量）连通分量（强连通分量）连通分量（强连通分量）非非连连通通图图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4无向图无向图G G 的极大连通子图称为的极大连通子图称为G G的连通分量。的连通分量。极大连通子图意思是：该子图是极大连通子图意思是：该子图是 G G 连通子图，将连通子图，将G G 的任何不在该子图中的顶点加入，子图不再连通。的任何不在该子图中的顶点加入，子图不再连通。V0V0 V2V2 V3V3 V1V1 V5V5 V4V4连通分量连通分量 2024年7月14日 有向图有向图G G 的极大强连通子图称为的极大强连通子图称为G G的强连通分量。的强连通分量。极大强连通子图意思是：该子图是极大强连通子图意思是：该子图是G G的强连通子图，的强连通子图，将将D D的任何不在该子图中的顶点加入，子图不再是的任何不在该子图中的顶点加入，子图不再是强连通的。强连通的。强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 2024年7月14日 极小连通子图极小连通子图极小连通子图极小连通子图：该子图是：该子图是G G 的连通子图，在该子图的连通子图，在该子图中删除任何一条边，子图不再连通。中删除任何一条边，子图不再连通。生成树：生成树：生成树：生成树：包含无向图包含无向图G G 所有顶点的极小连通子图。所有顶点的极小连通子图。生成森林：生成森林：生成森林：生成森林：对非连通图，由各个连通分量的生成树对非连通图，由各个连通分量的生成树的集合。的集合。连通图连通图 G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 2024年7月14日 6.2 6.2 图的存储结构图的存储结构邻接表邻接表邻接多重表邻接多重表十字链表十字链表链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：数组表示法（邻接矩阵）数组表示法（邻接矩阵）多重链表多重链表重点介绍：重点介绍：邻接矩阵邻接矩阵(数组数组)表示法表示法邻接表邻接表(链式链式)表示法表示法 2024年7月14日 v建立一个建立一个顶点表顶点表（记录各个顶点信息）（记录各个顶点信息）和一个和一个邻接矩邻接矩阵阵（表示各个顶点之间关系）（表示各个顶点之间关系）。v设图设图 A=(A=(V V,E E)有有 n n 个顶点，则图的邻接矩阵是个顶点，则图的邻接矩阵是一个二维数组一个二维数组 A.EdgennA.Edgenn，定义为：，定义为：数组（邻接矩阵）表示法数组（邻接矩阵）表示法 2024年7月14日 邻接矩阵：A.Edge=（v1v2v3v4v5）v1v2v3v4v50000000000000000000000000分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的；分析分析2 2：顶点顶点i i 的的度度第第 i i 行行(列列)中中1 1 的个数；的个数；特别：特别：完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余，其余1 1。01010101010101110101011100101010101010111010101110顶点表：无向图的邻接矩阵表示法无向图的邻接矩阵表示法v1v2v3v5v4v4 2024年7月14日 分析分析分析分析1 1 1 1：有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。分析分析分析分析2 2 2 2：顶点的顶点的出度出度=第第i i行元素之和行元素之和 顶点的顶点的入度入度=第第i i列元素之和列元素之和 顶点的顶点的度度=第第i i行元素之和行元素之和+第第i i列元素之和列元素之和 v1v2v3v4A A邻接矩阵：A.Edge=(v1v2v3v4)v1v2v3v40000000000000000注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧(即出度边）；即出度边）；第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧(即入度边）。即入度边）。顶点表：01100000000110000110000000011000有向图的邻接矩阵表示法有向图的邻接矩阵表示法 2024年7月14日 定义为：定义为：A.Edgeij=Wij或（或（vi,vj）VR无边（弧）无边（弧）v1v2v3v4Nv5v65489755613邻接矩阵：N.Edge=(v1v2v3v4v5v6)顶点表：57489565315748956531网（即有权图）的邻接矩阵表示法网（即有权图）的邻接矩阵表示法 2024年7月14日 优点：优点：容易实现图的操作，如：求某顶点的度、判容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。断顶点之间是否有边、找顶点的邻接点等等。缺点：缺点：n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边;空间效率为空间效率为O O(n(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵表示法的特点邻接矩阵表示法的特点 2024年7月14日 /用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#defineMaxInt32767/表示极大值，即表示极大值，即#defineMVNum100/最大顶点数最大顶点数typedefcharVerTexType;/假设顶点的数据类型为字符型假设顶点的数据类型为字符型typedefintArcType;/假设边的权值类型为整型假设边的权值类型为整型typedefstructVerTexTypevexsMVNum;/顶点表顶点表ArcTypearcsMVNumMVNum;/邻接矩阵邻接矩阵intvexnum,arcnum;/图的当前点数和边数图的当前点数和边数AMGraph;邻接矩阵的存储表示邻接矩阵的存储表示 2024年7月14日 v对每个顶点对每个顶点vi建立一个建立一个单链表单链表，把与，把与vi有关联的有关联的边的信息链接边的信息链接起来，每个结点设为起来，每个结点设为3个域；个域；vv每个单链表有一个每个单链表有一个每个单链表有一个每个单链表有一个头结点头结点头结点头结点（设为（设为（设为（设为2 2个域），存个域），存个域），存个域），存v vi i信息；信息；信息；信息；表结点表结点表结点表结点头结点头结点头结点头结点邻接点域邻接点域，表表示示vi一个邻接一个邻接点的位置点的位置链域链域，指向指向vi下一个边下一个边或弧的结点或弧的结点数据域数据域，与与边有关信息边有关信息（如权值）（如权值）数据域数据域，存存储顶点储顶点vi信信息息链域链域，指向，指向单链表的第单链表的第一个结点一个结点vv 每个单链表的每个单链表的每个单链表的每个单链表的头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储结构存储。结构存储。结构存储。结构存储。邻接表（链式）表示法邻接表（链式）表示法 2024年7月14日 13341420注：注：邻接表不唯一邻接表不唯一，因各个边结点的链入顺序是任意的，因各个边结点的链入顺序是任意的231420无向图的邻接表表示无向图的邻接表表示空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(en2 2)，比邻接矩阵表示法，比邻接矩阵表示法O(nO(n2 2)省空间。省空间。TD(Vi)=TD(Vi)=单链表中链接的结点个数单链表中链接的结点个数v1v2v3v5v4v4 2024年7月14日 v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)有向图的邻接表表示有向图的邻接表表示空间效率为空间效率为O(n+e)O(n+e)出度出度入度入度度：度：OD(Vi)OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数ID(Vi)ID(Vi)邻接点域为邻接点域为ViVi的弧个数的弧个数TD(Vi)=OD(Vi)+ID(Vi)2024年7月14日 8064125当邻接表当邻接表的存储结的存储结构形成后，构形成后，图便唯一图便唯一确定！确定！已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。2024年7月14日#defineMVNum100/最大顶点数最大顶点数typedefstructArcNode/边结点边结点intadjvex;/该边所指向的顶点的位置该边所指向的顶点的位置structArcNode*nextarc;/指向下一条边的指针指向下一条边的指针OtherInfoinfo;/和边相关的信息和边相关的信息ArcNode;typedefstructVNodeVerTexTypedata;/顶点信息顶点信息ArcNode*firstarc;/指向第一条依附该顶点的边的指针指向第一条依附该顶点的边的指针VNode,AdjListMVNum;/AdjList表示邻接表类型表示邻接表类型typedefstructAdjListvertices;/邻接表邻接表intvexnum,arcnum;/图的当前顶点数和边数图的当前顶点数和边数ALGraph;邻接表的存储表示邻接表的存储表示 2024年7月14日 优点：优点：空间效率高，容易寻找顶点的邻接点；空间效率高，容易寻找顶点的邻接点；缺点：缺点：判断两顶点间是否有边或弧，需搜索两结点判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。对应的单链表，没有邻接矩阵方便。邻接表表示法的特点邻接表表示法的特点 2024年7月14日 v1v2v3v5v4v44321013341420v5v4v3v2v1231420（v1v2v3v4v5）v1v2v3v4v5000000000000000000000000001010101010101110101011100101010101010111010101110邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2024年7月14日 2.2.区别：区别：对于任一确定的无向图，邻接矩阵是对于任一确定的无向图，邻接矩阵是唯一唯一的（行列的（行列号与顶点编号一致），但邻接表号与顶点编号一致），但邻接表不唯一不唯一（链接次序（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于邻接矩阵多用于稠密图稠密图；而邻接表多用于；而邻接表多用于稀稀疏图疏图邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系进阶任务进阶任务（完成每任务加经验值（完成每任务加经验值100）请把下面名词术语翻译成英文，并大声读与拼写请把下面名词术语翻译成英文，并大声读与拼写出来：出来：图图顶点顶点弧弧子图子图无向图无向图有向图有向图完全图完全图稀疏图稀疏图稠密图稠密图邻接点邻接点连通图连通图连通分量连通分量生成树生成树邻接矩阵邻接矩阵邻接表邻接表深度优先遍历深度优先遍历广度优先遍历广度优先遍历最短路径最短路径有向无环图有向无环图拓扑排序拓扑排序关键路径关键路径graphvertexarcsubgraphundirectedgraphdigraphcompletegraphsparesgraphdensegraphAdjacentconnectedgraphconnectedcomponentspanningtreeadjacencymatrixadjacencylistDepth-firstsearchbreadth-firstsearchshortestpathdirectedacyclicgraphtopologicalsortcriticalpath预习任务（200经验值）1.1.什么叫深度优先搜索遍历？什么叫深度优先搜索遍历？2.2.什么叫广度优先搜索遍历？什么叫广度优先搜索遍历？3.什么叫连通网的最小生成树？什么叫连通网的最小生成树？4.普里姆算法和克鲁斯卡尔算法的时间复杂度各是普里姆算法和克鲁斯卡尔算法的时间复杂度各是多少？它们适用于何种情况？多少？它们适用于何种情况？从图中某个顶点从图中某个顶点V0出发，访问此顶点，然后依次从出发，访问此顶点，然后依次从V0的各个未被访问的的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点有路径相通的顶点都被访问到。都被访问到。从图中的某个顶点从图中的某个顶点V0出发，并在访问此顶点之后依次访问出发，并在访问此顶点之后依次访问V0的所有未被的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和点，直至图中所有和V0有路径相通的顶点都被访问到。有路径相通的顶点都被访问到。在在e条带权的边中选取条带权的边中选取n-1条边（不构成回路），使条边（不构成回路），使“权值之和权值之和”为最小。为最小。普里姆，普里姆，O（n2），稠密图；克鲁斯卡尔，），稠密图；克鲁斯卡尔，O（eloge），稀疏图。），稀疏图。2024年7月14日 遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做问一次，就叫做图的遍历图的遍历图的遍历图的遍历，它是，它是，它是，它是图的图的基本运算基本运算。遍历实质：遍历实质：找每个顶点的邻接点的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在图中可能存在回路回路，且图的任一顶点都可，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边会沿着某些边又回到了曾经访问过的顶点又回到了曾经访问过的顶点。6.3 6.3 图的遍历图的遍历 2024年7月14日 图常用的遍历：图常用的遍历：深度优先搜索深度优先搜索广度优先搜索广度优先搜索解决思路：解决思路：设置设置辅助数组辅助数组 visitedvisited n n，用来标记每，用来标记每个被访问过的顶点。个被访问过的顶点。初始状态为初始状态为0 0i i 被访问，改被访问，改 visitedvisited i i 为为1 1，防止被多次访问，防止被多次访问怎样避免重复访问？怎样避免重复访问？2024年7月14日 基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。v1v1v2v3v8v7v6v4v5DFSDFS结果结果结果结果v2v4v8v5v3v6v7起点起点深度优先搜索深度优先搜索(DFS(DFS Depth_First Search)Depth_First Search)2024年7月14日 深度优先搜索的步骤深度优先搜索的步骤简单归纳：简单归纳：访问起访问起始点始点v v;若若v v的的第第1 1个个邻接点没访问过，邻接点没访问过，深度遍历深度遍历此邻接点；此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v v的第的第2 2个邻接点个邻接点重重新遍历。新遍历。2024年7月14日 深度优先搜索的步骤深度优先搜索的步骤详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点v 后，后，由由v 出发，访问出发，访问它的任一邻接顶它的任一邻接顶点点w1；E再从再从w1出发，访问出发，访问与与w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点w2；E然后再从然后再从w2出发，进行类似的出发，进行类似的访问，访问，E如此进行下去，直至到达所有如此进行下去，直至到达所有的邻接顶点都被访问过的顶点的邻接顶点都被访问过的顶点u 为止。为止。起点起点 2024年7月14日 深度优先搜索的步骤深度优先搜索的步骤详细归纳：详细归纳：E接着，退回一步，接着，退回一步，退到前一次刚退到前一次刚访问过的顶点访问过的顶点，看是否还有其它没，看是否还有其它没有被访问的邻接顶点。有被访问的邻接顶点。如果有，如果有，则访问此顶点，之后再则访问此顶点，之后再从此顶点出发，进行与前述类似的从此顶点出发，进行与前述类似的访问；访问；如果没有，如果没有，就就再退回一步再退回一步进行搜进行搜索。重复上述过程，直到连通图中索。重复上述过程，直到连通图中所有顶点都被访问过为止。所有顶点都被访问过为止。起点起点v2v1v3v5v4v6v2v1v3v5v4v6 2024年7月14日 讨论讨论1 1：计算机如何实现：计算机如何实现DFSDFS？DFSDFS结果结果结果结果邻邻接接矩矩阵阵A辅助数组辅助数组 visitedn起点起点v2v1v3v5v2v1v3v5v4v4v6v6开辅助数组开辅助数组 visitedn！2024年7月14日 voidDFS(AMGraphG,intv)/图图G为邻接矩阵类型为邻接矩阵类型coutv;visitedv=true;/访问第访问第v个顶点个顶点for(w=0;wG.vexnum;w+)/依次检查邻接矩阵依次检查邻接矩阵v所在的行所在的行if(G.arcsvw!=0)&(!visitedw)DFS(G,w);/w是是v的邻接点，如果的邻接点，如果w未访问，则递归调用未访问，则递归调用DFS讨论讨论讨论讨论2 2 2 2：DFSDFSDFSDFS算法如何编程？算法如何编程？算法如何编程？算法如何编程？可以用递归算法！可以用递归算法！2024年7月14日 讨论讨论讨论讨论3 3 3 3：在图的邻接表中如何进行：在图的邻接表中如何进行：在图的邻接表中如何进行：在图的邻接表中如何进行DFSDFSDFSDFS？v0v1v2v3v0v1v2v3DFSDFS结果结果结果结果辅助数组辅助数组 visitedn照样借用照样借用visitedn！起点起点0123 2024年7月14日 讨论讨论讨论讨论4 4 4 4：邻接表的：邻接表的：邻接表的：邻接表的DFSDFSDFSDFS算法如何编程？算法如何编程？算法如何编程？算法如何编程？voidDFS(ALGraphG,intv)/图图G为邻接表类型为邻接表类型coutadjvex;/表示表示w是是v的邻接点的邻接点if(!visitedw)DFS(G,w);/如果如果w未访问，则递归调用未访问，则递归调用DFSp=p-nextarc;/p指向下一个边结点指向下一个边结点仍可用递归算法仍可用递归算法abchdekfgFFFFFFFFFT T T T T T T TTach d kfe bgachkfedbg访问标志访问标志:访问次序访问次序:例如例如:a b c d e f g h k 2024年7月14日 n用用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点都要来表示图，遍历图中每一个顶点都要从头扫描从头扫描该顶点所在行，时间复杂度为该顶点所在行，时间复杂度为O(O(n n2 2)。n用用邻接表邻接表来表示图，虽然有来表示图，虽然有 2 2e e 个表结点，但只个表结点，但只需扫描需扫描 e e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n n个个头结点的时间，时间复杂度为头结点的时间，时间复杂度为O(O(n n+e e)。结论：结论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。DFSDFS算法效率分析算法效率分析 2024年7月14日 基本思想：基本思想：仿树的层次遍历过程仿树的层次遍历过程广度优先搜索广度优先搜索(BFS(BFS Breadth_First Search)Breadth_First Search)v1v1v2v3v8v7v6v4v5BFSBFS结果结果结果结果v2v3v4v5v6v7v8起点起点 2024年7月14日 简单归纳：简单归纳：在访问了在访问了起始点起始点v v之后，依次访问之后，依次访问 v v的邻接点的邻接点；然后再依次访问然后再依次访问这些顶点中未被访问过的邻接点这些顶点中未被访问过的邻接点；直到所有顶点都被访问直到所有顶点都被访问过为止。过为止。广度优先搜索是一种广度优先搜索是一种分层分层的搜索过程，每向前的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。那样有回退的情况。因此，广度优先搜索因此，广度优先搜索不是一个递归不是一个递归的过程，其的过程，其算法也不是递归的。算法也不是递归的。广度优先搜索的步骤广度优先搜索的步骤 2024年7月14日 讨论讨论1 1：计算机如何实现：计算机如何实现BFSBFS？邻接表邻接表除辅助数组除辅助数组visitedn外，外，还需再开一辅助队列还需再开一辅助队列起点起点辅助队列辅助队列v2已访问过了已访问过了BFS BFS 遍历结果遍历结果入队！入队！初始初始f=n-1,r=0f=n-1,r=0 2024年7月14日 （1 1）从图中某个顶点）从图中某个顶点v v出发，访问出发，访问v v，并置，并置visitedvisitedv v 的值为的值为truetrue，然后将，然后将v v进队。进队。（2 2）只要队列不空，则重复下述处理。）只要队列不空，则重复下述处理。队头顶点队头顶点u u出队。出队。依次检查依次检查u u的所有邻接点的所有邻接点w w，如果，如果visitedvisitedw w 的值为的值为falsefalse，则访问，则访问w w，并置，并置visitedvisitedw w 的值为的值为truetrue，然后将，然后将w w进队。进队。【算法思想算法思想】2024年7月14日 voidBFS(GraphG,intv)/按广度优先非递归遍历连通图按广度优先非递归遍历连通图Gcout=0;w=NextAdjVex(G,u,w)if(!visitedw)/w为为u的尚未访问的邻接顶点的尚未访问的邻接顶点coutw;visitedw=true;EnQueue(Q,w);/w进队进队/if/while/BFS【算法描述算法描述】2024年7月14日 如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（都要循环检测矩阵中的整整一行（n 个元素），总的个元素），总的时间代价为时间代价为O(n2)。用邻接表来表示图，虽然有用邻接表来表示图，虽然有2e个表结点，但只需扫描个表结点，但只需扫描e个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问n个头结点的时间，个头结点的时间，时间复杂度为时间复杂度为O(n+e)。BFSBFS算法效率分析算法效率分析 2024年7月14日 空间复杂度相同，都是空间复杂度相同，都是O(nO(n)(借用了堆栈或队列）；借用了堆栈或队列）；时间复杂度只与存储结构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有关，有关，而与搜索路径无关。而与搜索路径无关。DFSDFS与与BFSBFS算法效率比较算法效率比较 2024年7月14日 最小生成树最小生成树最短路径最短路径拓扑排序拓扑排序关键路径（自学）关键路径（自学）6.4 6.4 图的应用图的应用 2024年7月14日 极小连通子图极小连通子图极小连通子图极小连通子图：该子图是该子图是G G 的连通子图，在该子图中删除的连通子图，在该子图中删除任何一条边，子图不再连通。任何一条边，子图不再连通。生成树：生成树：生成树：生成树：包含图包含图G G所有顶点的极小连通子图（所有顶点的极小连通子图（n-1条边）条边）。G1G1的生成树的生成树连通图连通图 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小生成树最小生成树 2024年7月14日 DFSDFS生生成成树树邻邻接接表表13341420v4v3v2v1v0231420v0v2v1v4v3BFSBFS生生成成树树v0v1v3v2v4无向连通图无向连通图画出下图的生成树画出下图的生成树v0v1v2v4v4v3 2024年7月14日 求最小生成树求最小生成树首先明确首先明确：使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树的生成树有有 n n 个顶点、个顶点、n-n-1 1 条边。条边。目标：目标：在网的多个生成树中，寻找一个在网的多个生成树中，寻找一个各边各边权值之和最小权值之和最小的生成树的生成树 2024年7月14日 v必须只使用该必须只使用该网中的边网中的边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n-1n-1条边条边来联结网络中的来联结网络中的n n个个顶点顶点v不能使用产生不能使用产生回路回路的边的边构造最小生成树的准则构造最小生成树的准则 2024年7月14日 欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条条线路；但因为每条线路都会有对应的经济成本，而线路；但因为每条线路都会有对应的经济成本，而n n个个城市可能有城市可能有n(n-1)/2 n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条条线路，使总费用最少？线路，使总费用最少？数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n n1 1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显然此连通网显然此连通网是一个是一个生成树生成树！最小生成树的典型用途最小生成树的典型用途 2024年7月14日 vPrimPrim（普里姆）算法（普里姆）算法 vKruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法PrimePrime算法算法:归并顶点归并顶点，与边数无关，适于，与边数无关，适于稠密网稠密网Kruskal算法：算法：归并边归并边，适于，适于稀疏网稀疏网如何求最小生成树如何求最小生成树 2024年7月14日 设连通网络设连通网络N=V,E1.1.从从从从某某某某顶顶顶顶点点点点 u u0 0 出出出出发发发发，选选选选择择择择与与与与它它它它关关关关联联联联的的的的具具具具有有有有最最最最小小小小权权权权值值值值的的的的边边边边(u u0 0,v v)，将将将将其其其其顶顶顶顶点点点点加加加加入入入入到到到到生生成成树树的的顶顶点点集集合合U中中中中2.2.每每每每一一一一步步步步从从从从一一一一个个个个顶顶顶顶点点点点在在在在U U中中中中，而而而而另另另另一一一一个个个个顶顶顶顶点点点点不不不不在在在在U U中中中中的的的的各各各各条条条条边边边边中中中中选选选选择择择择权权权权值值值值最最最最小小小小的的的的边边边边(u,(u,v),v),把把把把它它它它的的的的顶顶顶顶点点点点加入到加入到加入到加入到U中中中中3.3.直到所有顶点都加入到生成树顶点集合直到所有顶点都加入到生成树顶点集合直到所有顶点都加入到生成树顶点集合直到所有顶点都加入到生成树顶点集合U U中为止中为止中为止中为止普里姆算法的基本思想普里姆算法的基本思想归并顶点归并顶点 2024年7月14日 应用普里姆算法构造最小生成树的过程应用普里姆算法构造最小生成树的过程abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+21=67abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 5a b c d e f g 2024年7月14日 设连通网络设连通网络N=V,E1.构构造造一一个个只只有有n 个个顶顶点点，没没有有边边的的非非连连通通图图T=V,每个顶点自成一个连通分量每个顶点自成一个连通分量2.在在E 中中选选最最小小权权值值的的边边,若若该该边边的的两两个个顶顶点点落落在在不不同同的的连连通通分分量量上上，则则加加入入T 中中；否否则则舍舍去去，重新选择重新选择3.重重复复下下去去，直直到到所所有有顶顶点点在在同同一一连连通通分分量量上上为止为止克鲁斯卡尔算法的基本思想克鲁斯卡尔算法的基本思想归并边归并边 2024年7月14日 应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程abcdegf195141827168213ae12dcbgf7148531621例如例如:7121819课堂任务（200经验值）无向图有个结点和条边，并依次输入无向图有个结点和条边，并依次输入这条边为（，），（，），（，这条边为（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，）（1 1）请按）请按头插法头插法画出的邻接表画出的邻接表（2 2）根据你的邻接表从）根据你的邻接表从顶点顶点出发，分别出发，分别写出按深度优先搜索法和广度优先搜索法进写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列，并画出其相应的深度优行遍历的结点序列，并画出其相应的深度优先生成树与广度优先生成树。先生成树与广度优先生成树。（，），（，），（，），（，（，），（，），（，），（，），（，），（，），（，），），（，），（，），（，），（，），（，）（，），（，）解：（1）G的邻接表：（2）从3出发深度遍历为：从3出发广度遍历为：3 4 5 0 2 13 4 2 5 0 1深度优先生成树广度优先生成树预习任务（经验值预习任务（经验值200）1.拓扑排序定义是什么？拓扑排序是意义拓扑排序定义是什么？拓扑排序是意义是什么？是什么？2.求最短路径有何现实意义？求最短路径有何现实意义？3.Dijkstra算法的思路是什么？算法的思路是什么？4.Floyd算法的思路是什么？算法的思路是什么？按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。判断图是否有环。序关系的顶点，则可以人为加上任意的次序关系。判断图是否有环。依最短路径的长度递增的次序求得各条路径依最短路径的长度递增的次序求得各条路径从从vi到到vj的所有可能存在的路径中，选出一条长度的所有可能存在的路径中，选出一条长度最短的路径最短的路径GPS、人工智能自动寻路、路由管理等、人工智能自动寻路、路由管理等 2024年7月14日 用有向图来描述一个工程或系统的进行过程。用有向图来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只要完成了这些子工程一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成。（活动），就可以导致整个工程的完成。AOVAOV网网(Activity On Vertices)(Activity On Vertices)用用顶点顶点表示活动的网络表示活动的网络 AOEAOE网网(Activity On Edges)(Activity On Edges)用用边边表示活动的网络表示活动的网络比如教学计划的制定比如教学计划的制定哪些课程是必须先修的，哪些课程是可以并行学习的。哪些课程是必须先修的，哪些课程是可以并行学习的。有向无环图及其应用有向无环图及其应用 2024年7月14日 C1高等数学高等数学C2程序设计基础程序设计基础C3离散数学离散数学C1,C2C4数据结构数据结构C3,C2C5高级语言程序设计高级语言程序设计C2C6编译方法编译方法C5,C4C7操作系统操作系统C4,C9C8普通物理普通物理C1C9计算机原理计算机原理C8 2024年7月14日 学生课程学习工程图学生课程学习工程图数据结构数据结构数据结构数据结构离散数学离散数学离散数学离散数学程序设计基础程序设计基础程序设计基础程序设计基础对学生选课工程图进行拓扑排序，得到的拓扑有序序列为对学生选课工程图进行拓扑排序，得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或或C1,C8,C9,C2,C5,C3,C4,C7,C6 2024年7月14日 1.输入输入AOV网络。令网络。令n 为顶点个数。为顶点个数。2.在在AOV网络中网络中选一个没有直接前驱的顶点选一个没有直接前驱的顶点,并输出之并输出之;3.从图中删去该顶点从图中删去该顶点,同时删去所有它发出的有向边同时删去所有它发出的有向边;4.重复以上重复以上2、3步步,直到：直到：1.全部顶点均已输出，拓扑有序序列形成，拓扑排序全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或：完成；或：2.图中还有未输出的顶点，但已跳出处理循环。这说图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时找不到没有前驱的顶点了。这时AOV网络中必定存网络中必定存在有向环。在有向环。拓扑排序算法的思想拓扑排序算法的思想重复选择没有直接前驱的顶点重复选择没有直接前驱的顶点abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念没有前驱的顶点没有前驱的顶点入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧弧头顶点的入度减弧头顶点的入度减1 2024年7月14日 典型用途：典型用途：交通问题。如：城市交通问题。如：城市A A到城市到城市B B有多条线路，有多条线路，但每条线路的交通费（或所需时间）不同，那么，但每条线路的交通费（或所需时间）不同，那么，如何如何选择一条线路，使总费用（或总时间）最少？选择一条线路，使总费用（或总时间）最少？问题抽象：问题抽象：在在带权有向图带权有向图中中A A点（源点）到达点（源点）到达B B点（终点）点（终点）的多条路径中，寻找一条的多条路径中，寻找一条各边权值之和最小各边权值之和最小的路径，即的路径，即最短路径。最短路径。（注：最短路径与最小生成树不同，路径上（注：最短路径与最小生成树不同，路径上不一定包含不一定包含n n个顶点）个顶点）最短路径最短路径 2024年7月14日 一顶点到其一顶点到其余各顶点余各顶点两种常见的最短路径问题：两种常见的最短路径问题：一、一、单源最短路径单源最短路径用用Dijkstra（迪杰斯特拉）（迪杰斯特拉）算法算法二、所有顶点间的最短路径二、所有顶点间的最短路径用用Floyd（弗洛伊德）（弗洛伊德）算法算法任意两顶任意两顶点之间点之间 2024年7月14日 目的：目的：设一设一有向图有向图G=G=（V,EV,E），已知各边的权值，以某指），已知各边的权值，以某指定点定点v v0 0为源点，求从为源点，求从v v0 0到图的其余各点的最短路径。到图的其余各点的最短路径。限定各限定各边上的权值大于或等于边上的权值大于或等于0 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算法）算法）2024年7月14日 v0(v0,v1)10源点源点终点终点最最短短路路径径路径长度路径长度(v0,v1,v2)(v0,v3,v2)(v0,v3)30 v1 v2 v3 v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例例2 2：6001234 5090 70讨论：计算机如何自动求出这些最短路径？讨论：计算机如何自动求出这些最短路径？(v0,v1,v2,v4)60 2024年7月14日 先找出从源点先找出从源点v v0 0到各终点到各终点v vk k的直达路径（的直达路径（v v0 0,v,vk k），即），即通过一条弧到达的路径。通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（从这些路径中找出一条长度最短的路径（v v0 0,u,u）,然后然后对其余各条路径进行适当调整：对其余各条路径进行适当调整：若在图中存在弧（若在图中存在弧（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算法的思想算法的思想V0V1V2V3V4V5510502030601010010023010004052,600234,5004390045求每一对顶点之间的最短路径求每一对顶点之间的最短路径弗洛伊德弗洛伊德算法的基本思想是：算法的基本思想是：从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径ABC642113ABC642113ABC642113ABC6421136.4.4关键路径（自学）关键路径（自学）问题问题:假设以有向网表示一个施工流图，弧假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。上的权值表示完成该项子工程所需时间。问：哪些子工程项是问：哪些子工程项是“关键工程关键工程”？即：哪些子工程项将影响整个工程的完成即：哪些子工程项将影响整个工程的完成期限的。期限的。abcdefghk64521187244例如例如:“关键活动关键活动”指的是指的是：该弧上的：该弧上的权值增加权值增加将将使有向图上的使有向图上的最长路径的长度增加。最长路径的长度增加。整个工程完成的时间为整个工程完成的时间为：从有向图的：从有向图的源点源点到到汇点汇点的最长路径。的最长路径。源点源点汇点汇点6174 2024年7月14日 图图存储结构存储结构遍遍 历历邻接矩阵邻接矩阵邻邻接接表表深度优先搜索深度优先搜索DFS广度优先搜索广度优先搜索BFS无向图的应用无向图的应用应用应用最小生成树最小生成树Prim算法算法Kruskal算法算法有向图的应用有向图的应用活动网络活动网络AOV：拓扑排序算法：拓扑排序算法AOE：关键路径：关键路径最短路径最短路径Dijkstra算法算法Floyd算法算法小结小结 2024年7月14日 1.1.掌握：图的基本掌握：图的基本概念及相关术语和性质概念及相关术语和性质2.2.熟练掌握：图的熟练掌握：图的邻接矩阵和邻接表邻接矩阵和邻接表两种存储两种存储表示方法表示方法3.3.熟练掌握：图的两种遍历方法熟练掌握：图的两种遍历方法DFSDFS和和BFSBFS4.4.熟练掌握：最短路算法（熟练掌握：最短路算法（Dijkstra算法算法）5.5.掌握：掌握：最小生成树最小生成树的两种算法的思想及的两种算法的思想及拓扑拓扑排序排序算法的思想算法的思想小结小结进阶任务进阶任务（完成每任务加经验值（完成每任务加经验值100）教材教材P160页，页，1选择题选择题（1）在一个图中，所有顶点的度数之和等于图的边数）在一个图中，所有顶点的度数之和等于图的边数的（的（）倍。）倍。A1/2B1C2D4（2）在一个有向图中，所有顶点的入度之和等于所有）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（顶点的出度之和的（）倍。）倍。A1/2B1C2D4（3）具有）具有n个顶点的有向图最多有（个顶点的有向图最多有（）条边。）条边。AnBn(n-1)Cn(n+1)Dn2进阶任务进阶任务（完成每任务加经验值（完成每任务加经验值100）教材教材P160页，页，1选择题选择题（4）n个顶点的连通图用邻接距阵表示时，该距阵至个顶点的连通图用邻接距阵表示时，该距阵至少有（少有（）个非零元素。）个非零元素。AnB2(n-1)Cn/2Dn2（5）G是一个非连通无向图，共有是一个非连通无向图，共有28条边，则该图至条边，则该图至少有（少有（）个顶点。）个顶点。A7B8C9D10（6）若从无向图的任意一个顶点出发进行一次深度优）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是先搜索可以访问图中所有的顶点，则该图一定是（）图。）图。A非连通非连通B连通连通C强连通强连通D有有向向进阶任务进阶任务（完成每任务加经验值（完成每任务加经验值100）教材教材P160页，页，1选择题选择题（7）下面（）算法适合构造一个稠密图）下面（）算法适合构造一个稠密图G的最小生的最小生成树。成树。APrim算法算法BKruskal算法算法CFloyd算法算法DDijkstra算法算法（8）用邻接表表示图进行广度优先遍历时，通常借助）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。）来实现算法。A栈栈B.队列队列C.树树D图图（9）用邻接表表示图进行深度优先遍历时，通常借助）用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。）来实现算法。A栈栈B.队列队列C.树树D图图进阶任务进阶任务（完成每任务加经验值（完成每任务加经验值100）教材教材P160页，页，1选择题选择题（10）深度优先遍历类似于二叉树的（）深度优先遍历类似于二叉树的（）。）。A先序遍历先序遍历B中序遍历中序遍历C后序遍历后序遍历D层次遍历层次遍历（11）广度优先遍历类似于二叉树的（）广度优先遍历类似于二叉树的（）。）。A先序遍历先序遍历B中序遍历中序遍历C后序遍历后序遍历D层次遍历层次遍历（12）图的）图的BFS生成树的高比生成树的高比DFS生成树的高（）。生成树的高（）。A小小B相等相等C小或相等小或相等D大或相大或相等等进阶任务进阶任务（完成每任务加经验值（完成每任务加经验值100）教材教材P160页，页，1选择题选择题（13）已知图的邻接矩阵如图）已知图的邻接矩阵如图6.25所示，则从顶点所示，则从顶点0出发按深度优先遍历的结果是（出发按深度优先遍历的结果是（）。）。A0243156B0136542C01