数据结构（Java语言版）（第2版）（微课版） 教案8-4：图的拓扑排序及关键路径

授课题目第8章图的拓扑排序及关键路径授课时间授课学时22学时授课地点授课形式理论教学目标知识目标能力目标素质目标学情分析已有基础：学生已理解图的基本概念、遍历等算法，具备一定的算法基础与工程问题分析能力；发展进阶：学生将AOV网及AOE网的概念，并能解决实际的的图/网问题；学习障碍：理解最早开始时间、最晚开始时间等概念，将实际问题抽象为拓扑排序或关键路径问题可能需要一定的经验和技巧；教学内容教学重点解决方法1.通过详细的讲解和示例演示，让学生清晰理解算法的每一个步骤；2.布置练习题和实际项目案例，让学生在实践中掌握算法的应用；教学难点1.理解拓扑排序中入度的计算和更新2.关键路径算法中最早开始时间、最晚开始时间等参数的计算解决方法1.利用动画、图示等多媒体手段进行直观展示，帮助学生理解复杂的计算过程；2.组织学生进行小组讨论，互相交流和解释计算过程，加深理解；教学策略学习方法1.课前（1）预习法：查看预习资料，了解实际应用；（2）复习法：复习图的概念、遍历算法；2.课上（1）讲授法：通过教师讲解和演示，引导学生理解相关知识点，强化学生对图的具体应用；（2）小组讨论法：分析问题，制定解决方案，然后进行交流和分享，教师进行点评和总结；（3）归纳总结：对AOV网及AOE网及算法、工程示例进行总结归纳。3.课后（1）练习法：以作业为载体对本讲知识进行巩固；教学资源

教学过程教学环节及时间教学内容教师活动学生活动设计意图课前复习：图的概念、遍历算法；预习：查看预习资料，了解AOV网及AOE网概念、拓扑排序和关键路径原理以及实际应用；思考：拓扑排序和关键路径在生活中的实例应用？1.发布并布置学习任务；2.推送相关学习资源；3.开启课前答疑讨论活动。1.接受并查看课前学习任务；2.完成课前讨论；1.通过复习已学知识点，为完成本次学习任务奠定知识基础；2.通过预习，了解拓扑排序和关键路径算法及应用；课中环节一导言（5分钟）问题：我们在穿衣服的时候都有一定的顺序，我们可以把这种顺序想成，衣服与衣服之间有一定的依赖关系。假设我们现在有八件衣服要穿，它们之间的两两依赖关系我们已经很清楚了，那如何安排一个穿衣序列？1.展示一个项目流程的有向图示例；2.提问：如何确定项目中各任务的执行顺序？1.观察有向图；

2.思考老师的问题，尝试回答；引发学生兴趣，引入拓扑排序和关键路径的概念。课中环节二目标（5分钟）1.本讲内容的目标，包括知识目标、能力目标和素质目标；2.本讲内容的重点、难点内容；3.本将内容的学习方法；1.展示本次课程的学习目标、重点和难点内容；2.介绍和强调本次课程的学习方法；1.熟悉本次课程需要巩固的知识、提高的技能、提升的认识；2.理解学习本次课程的目的和意义以及方法途径；通过展示本次学习目标让学生理解学习本次课程的目的、意义和实现途径。将教师教的目标转化为学生学的目标。课中环节三介绍性讲解（75分钟）知识点1：拓扑排序（30分钟）核心知识点：（1）拓扑排序概念（2）拓扑排序算法素质点：通过此部分知识培养学生逻辑思维能力、程序算法能力；通过讨论，培养1.讲解拓扑排序的定义和作用；

2.结合示例，逐步说明拓扑排序的步骤；3.在黑板上或通过多媒体演示拓扑排序算法；4.解释算法中关键步骤和数据结构的使用；5.布置练习，让学生对给定的有向图进行拓扑排序。6.巡视指导，解答学生问题。1.认真听讲，理解概念；

2.跟随示例，思考排序过程；3.仔细观察演示；4.提出疑问，与老师互动；5.独立完成练习。

6.小组讨论，互相交流思路1.使学生掌握拓扑排序的基本概念；2.帮助学生理解算法的实现过程；3.巩固学生对拓扑排序的掌握和应用；知识点2：关键路径（30分钟）核心知识点：（1）关键路径概念（2）关键路径算法素质点：通过此部分知识培养学生逻辑思维能力、程序算法能力；通过讨论，培养1.引入关键路径的概念，强调其在项目管理中的重要性；

2.解释关键路径的定义和计算方法；3.详细演示关键路径算法的计算过程；4.强调算法中的关键参数和逻辑；1.专注听讲，理解关键路径的意义；

2.对比拓扑排序，思考两者的区别与联系；3.认真观察，记录要点；4.思考算法的复杂性和优化方向；1.使学生明确关键路径的概念和用途；2.帮助学生掌握关键路径算法的计算；知识点3：综合案例（15分钟）核心知识点：综合案例分析素质点：通过案例分析，培养工程意识。1.社交网络分析是一个复杂的问题，需要对大量的数据进行排序和分析。2.软件开发项目分析，关键路径法可以帮助团队确定各个模块的完成时间和依赖关系，从而合理安排开发进度，确保软件按时发布。3.引导学生同时运用拓扑排序和关键路径算法进行分析；1.小组合作，完成案例分析；

2.展示成果，分享思路和方法；培养学生综合运用知识解决实际问题的能力。课中环节五总结（5分钟）总结：布置课后学习任务；课后1.对课程内容进行复习，对易错点进行分类汇总；2.完成课后作业习题；