《数据结构[Python语言描述]》教案第14课图（7.4-7.7）.docx

课题第14课图(7.4-7.7)课时2课时(90min)教学目标知识目标：掌握图的应用，包括最小生成树、最短路径、拓扑排序和关键路径技能目标：(1)能利用图解决实际应用中的最短路径问题(2)能利用AOE网预估一个工程的完工时间素质目标：树立全局意识，学会抓住关键，并利用关键环节掌控全局进展教学重难点教学重点：最小生成树的算法、求最短路径的算法、求解关键路径的步骤教学难点：最小生成树的算法、求最短路径的算法教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：什么是最小生成树？【蚂思考、传授新知【教师】通过学生的回答引入要讲的知识，介绍最小生成树、最短路径,拓扑排序和关催路径7.4最小生成树在一个无向连通网的所有生成树中，各条边权值之和最小的生成树称为该无向连通网的最小生成树.构造最小生成树时，需要遵循如下3条原则.(1)尽可能选取权值最小的边，但不能构成回路。(2)最小生成树应具有n个顶点和n-l条边。(3)最小生成树一定是连通的。常用的构造最小生成树的算法有Prim算法和Kruskal算法。7.4.1Prim算法假设N=(V,E)是一个无向连通网，其中V为顶点集，E为边集。另设置两个集合U和TE,令U为最小生成树的顶点集，TE为最小生成树的边集，则使用Prim算法求最小生成树T的步骤如下。(1)令U的初始值为U=uO)(uOV),TE的初始值为TE=(2)在所有uU,vV-U的边(u,v)E中选择一条权值最小的边(U(XVO),并将其加入TE中，同时将顶点VO加入U中。(3)重复步骤(2),直到U=V。此时，TE中必含有n-l条边，T=(U,TE)即为N的最小生成树。【算法描述】详见教材÷【教师】讲解实例72(详见教材)【提示】在选择权值最小的边时，可能出现多条边权值相同的情况，此时可任选其一，因此无向连通网的最小生成树不一定是唯一的。7.4.2Kruskal算法假设N=(V,E)是一个无向连通网，其中V为顶点集，E为边集，则使用Kruskal算法求最小生成树T的步骤如下。(1)令N的最小生成树T的初始状态为T=(V,),即T由V中的n个顶点构成，顶点之间不存在边。(2)在E中选择权值最小的边(u.v),若该条边未使最小生成树T形成回路，则将其加入T中，否则舍去该条边。(3)重复步骤(2),直到T中所有顶点构成一个连通分量(或者包含n-1条边).KrUSkal算法的关键是判断选择一条权值最小的边后最小生成树是否会形成回路，这可以通过判断该条边的两个顶点所在的连通分量是否相同来解决。÷【教师】随机邀请学生回答以下问题KrUSkal算法的判断规则是什么？÷【学生】聆听、思考、回答判断规则为，每个连通分量用其中一个顶点的编号来标识(称为连通分量编号)，同一个连通分量中所有顶点的连通分量编号相同，不同连通分量中两个顶点的连通分量编号不相同。如果选择的边的两个顶点的连通分量编号相同，则一定会形成回路，此时，须舍弃该条边。【算法描述】详见教材÷【教师】讲解实例7-3(详见教材)7.5 最短路径计【教师】随机邀请学生回答以下问题什么是最短路径？÷【学生】聆听、思考、回答在带权图中，路径长度不再是一条路径中经过的边的数目，而是所经过边的权值之和。从一个顶点到另一个顶点可能存在多条路径，其中权值之和最小的路径称为最短路径。实际中很多问题都可以看作图的最短路径问题，如求城市A到城市B的最短行驶8巨离。常用的求最短路径的算法有Dijkstra算法和Floyd算法。7.5.1 Dijkstra算法Dijkstra算法可解决有向网中从源点v到其他顶点的最短路径问题。假设G=(KE)是一个有向网，其中，V为顶点集，E为边集。如果用S表示已求得最短路径的顶点集,用U表示尚未求得最短路径的顶点集，则使用Dijkstra算法求最短路径的步骤如下。(1)初始时，S中只有源点v,U中是除源点v之外的其他顶点。(2)从U中找出源点v到U中最短路径长度最小的顶点u,并将其加入S中。(3)以顶点u为中间点，此时从源点v到某个顶点(假设为顶点Vl)的最短路径有两条，一条经过顶点U；另一条不经过顶点Ue(4)重复步骤(2)和步骤(3),直到所有顶点均加入S中。【算法描述】详见教材÷【教师】讲解实例7-4(详见教材)7.5.2 Floyd算法Floyd算法可解决有向网中任意两个顶点之间的最短路径问题。Floyd算法可以使用n阶方阵来描述，其中D-li(jl表示从顶点i出发不经过其他顶点直接到达顶点j的路径长度,D(k)i(11表示从顶点i到顶点j的中间可能经过顶点0、1、k,但不经过顶点k+1、k+2、n-1的最短路径长度。所以，Floyd算法的求解过程是按照图中顶点的顺序依次计算D(k)(0kn-l),最终得到的D(n-l)ij就是从顶点i到顶点j的最短路径长度。【算法描述】详见教材【教师】讲解实例7-5(详见教材)7.6 拓扑排序在实际生活中，一项工程往往可以分解为多个子任务(称为“活动”)，且这些子任务之间存在着一定的相互制约关系，如其中某些子任务必须在另一些子任务完成之后才能开始.*【教师】多媒体展示“计算机专业的相关课程”表7-4中课程之间优先关系的有向图“(详见教材)，并介绍拓扑排序由表可以看出，这些课程(活动)之间存在优先关系，如学生在学习数据结构之前须先学习程序设计基础和离散数学.表中课程之间的这种优先关系可以用有向图表示，如图所示.图中顶点表示课程编号，有向边表示课程之间的优先关系。如果课程i在课程j前完成，则存在边i,j。如果用一个有向图的顶点表示活动，用弧表示活动之间的优先关系，则将这样的有向图称为用顶点表示活动的网络，简称AOV网。【提示】由于AOV网中的每个顶点代表的是一项活动，如果存在回路就意味着某个活动的开始是以自身的完成为约束，这显然是矛盾的。因此，在AoV网中不允许出现环(回路)。拓扑排序就是将AOV网中的各个顶点排列成一个有序序,并称此序列为拓扑序【教师】随机邀请学生回答以下问题拓扑排序需要满足哪些条件？【学生】聆听、思考、回答拓扑排序需要满足如下两个条件。(1)每个顶点出现且只出现一次。(2)若Vi,V1是一条从顶点W到顶点号的弧，则在拓扑序列中，顶点叫必定在顶点之前。拓扑排序的步骤如下.(1)在有向图中选择一个入度为0的顶点并输出。(2)删除该顶点及所有以该顶点为弧尾的弧。(3)重复执行步骤(I)和步骤(2),直到输出所有顶点。【算法描述】详见教材【小技巧】删除顶点及所有以该顶点为弧尾的弧时，无须真而寸图的存储结构进行改变，只需将相关的弧头顶点(该顶点的每个邻接点)的入度减1即可。【教师】讲解实例7-6(详见教材)7.7关键路径7.7.1 AOE网在一个描述工程预计进度的带权有向图中,用顶点表示事件，用有向边(弧)表示活动,用边的权值表示活动持续的时间，这种构造的有向无环图称为用边表示活动的网络，简称AOE网。AOE网的基本术语如下。(1)源点：表示整个工程的开始，即图中唯一的、入度为0的顶点。(2)汇点：表示整个工程的结束,即图中唯一的、出度为0的顶点。.(详见教材)7.7.2 求解关键路径关键路径是指AOE网中从源点到上匚点的所有路径中边的权值之和最大的路径。1.关键路径的基本术语在求解关键路径前，首先了解如下几个基本术语。(1)事件vi的最早发生时间。从源点对到顶点V,的最长路径长度称为事件党的最早发生时间，一般记作ve(i)。计算咫力的方法是从源点开始，按拓扑JI顺序向心点递推。通常将源点的最早发生时间定义为0,故有：Ve(O)=Ove()=Maxve(k)+dut(<k>),<kJ>T,111-1其中，7是所有以口为弧头的弧的集合，加(4>)是弧<3的权值，即弧对应的活动的持续时间。(2)事件v1的最晚发生时间。在保证整个工程完成的前提下，事件“必须发生的时间称为事件力的最晚发生时间，一般记作vl(i)9计算以/)的方法是在收/)的基础上，从汇点开始，按逆拓扑顺序向源点递推，故有：v(n-l)=ve(11-l)vl(i)=Minvl(k)-dut<i,k>),<i,k>S,0n-2其中，5是所有以力为弧尾的弧的集合，如«</；Q)是弧<，；>的权值,即弧<，；Q对应的活动的持续时间。(3)活动卬的最早开始时间。如果活动a对应的弧为<j,k>,则活动。的最早开始时间等于事件Vj的最早发生时间，一般记作e(i),即e(i)=ve(j)1,(4)活动办的最晚开始时间。如果活动0对应的弧为<j,k>,则活动,的最晚开始时间等于事件取的最晚发生时间与活动cii的持续时间dut(<j,k>)之差，一般记作l(i),即Ki)=VKk)-dW<j,k>)°(5)活动S的时间余量。活动的时间余量等于活动小的最晚开始时间与活动S的最早开始时间之差。(6)关键活动。时间余量为0的活动。2.求解关键路径的步骤求解关键路径的步骤如下。(I)求出AOE网的一个拓扑序列。(2)从源点开始，按拓扑序列求出各事件的最早发生时间ve(i)(0in-l)(3)从汇点开始，按逆拓扑序列求出各事件的最晚发生时间vl(i)(O<i<n-1)(4)根据每个事件的最早发生时间ve(i)和最晚发生时间vl(i),求出各活动ai的最早开始时间e(i)和最晚开始时间l(i)(5)若活动ai满足e(i)=l(i),则活动ai为关键活动。由关键活动形成的由源点到汇点的路径就是关键路径。【算法描述】详见教材*【教师】讲解实例77（详见教材）【学生】聆听、思考、理解、记录任务实施任务一求城市之间交通费用最少的路线【教师】描述问题，分析问题，安排学生扫描微课二维码观看视频“求城市之间交通费用最少的路线“（详见教材），要求学生设计算法【问题描述】已知图7-26（详见教材）为一个城市交通网，其中各顶点表示城市，边的权值表示从一个城市到另一个城市的交通费用.现有T立旅客要从城市A到其他城市，设计算法找出一条路线，使得这位旅客从城市A到其他城市所花费的交通费用最少。【问Sg分析】该问题反映在图上就是要找从顶点A到其他顶点的最短路径，因此可以使用Dijkstra算法求解该问题，并用从顶点A到其他顶点的最短路径及最短路径长度表示从城市A到其他城市在交通费用最少情况下的路线及花销。【学生】自行扫码观看配套微课，按照要求完成任务，如遇问翘可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点最小生成树：Prim算法、Kruskal算法最短路径：Dijkstra算法、Floyd算法拓寺脚序关键路径：AOE网、求解关键路径【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的剩余练习。【学生】完成课后任务教学反思