数据结构（Java语言版）（第2版）（微课版） 教案8-3：图的生成树及最短路径

授课题目第8章图的生成树及最短路径授课时间授课学时22学时授课地点授课形式理论教学目标知识目标能力目标素质目标学情分析已有基础：学生已理解图的基本概念、遍历算法，树的基本概念、的基本操作，具备一定的算法基础；发展进阶：学生将理解掌握生成树算法，分析最小生成树、最短路径问题，并使用这些算法在解决某些复杂的图/网问题；学习障碍：最小生成树等算法的原理和实现细节较为复杂，算法的实现需要较强的编程能力，将生成树算法应用到实际问题中需要一定的领域知识和实践经验，学生在此部分学习存在困难；教学内容教学重点解决方法通过生动的例子和直观的演示来讲解生成树的概念、性质和算法原理。教学难点解决方法利用图表、动画等多媒体手段帮助学生理解抽象的概念和复杂的算法步骤。教学策略学习方法1.课前（1）预习法：查看预习资料，了解图的生成树算法、图的实际应用；（2）复习法：复习图的概念、遍历算法；2.课上（1）讲授法：通过教师讲解和演示，引导学生理解相关知识点，强化学生对图的具体应用；（2）小组讨论法：分析问题，制定解决方案，然后进行交流和分享，教师进行点评和总结；（3）归纳总结：对prim算法、Dijkstra算法进行总结归纳。3.课后（1）练习法：以作业为载体对本讲知识进行巩固；（2）总结巩固：总结、复盘，实现知识的内化和思想的升华。教学资源

教学过程教学环节及时间教学内容教师活动学生活动设计意图课前复习：图的概念、遍历算法；预习：查看预习资料，了解图的生成树算法、图的实际应用；思考：生成树在生活中的实例应用？1.发布并布置学习任务；2.推送相关学习资源；3.开启课前答疑讨论活动。1.接受并查看课前学习任务；2.完成课前讨论；1.通过复习已学知识点，为完成本次学习任务奠定知识基础；2.通过预习，了解生成树算法及应用；课中环节一导言（5分钟）问题：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，如何使铺设光缆的总费用最低？1.展示一个复杂的图示例。

2.提问：如果要确保网络中的所有节点都能连通，同时线路尽量简单，应该怎么做？1.观察图的结构。

2.思考老师的问题，尝试回答。引起学生兴趣，引导学生思考生成树的概念。课中环节二目标（5分钟）1.本讲内容的目标，包括知识目标、能力目标和素质目标；2.本讲内容的重点、难点内容；3.本将内容的学习方法；1.展示本次课程的学习目标、重点和难点内容；2.介绍和强调本次课程的学习方法；1.熟悉本次课程需要巩固的知识、提高的技能、提升的认识；2.理解学习本次课程的目的和意义以及方法途径；通过展示本次学习目标让学生理解学习本次课程的目的、意义和实现途径。将教师教的目标转化为学生学的目标。课中环节三介绍性讲解（75分钟）知识点1：图的生成树（15分钟）核心知识点：图的生成树概念素质点：培养学生的合作能力和应用知识的能力。1.讲解生成树的定义和特点；

2.以简单图为例，通过画图展示生成树的多种可能形式；3.提出问题：生成树在实际生活中的应用有哪些？

4.组织学生分组讨论。1.认真听讲，理解生成树的概念；

2.观察示例，明确生成树的结构特征；3.小组成员积极讨论，分享想法。

4.每组推选代表进行发言。让学生掌握生成树的基本概念；培养学生的合作能力和应用知识的能力。知识点2：最小生成树（30分钟）核心知识点：（1）最小生成树的基本概念（2）prim算法（3）Kruskal算法素质点：通过此部分知识培养学生逻辑思维能力、程序算法能力；通过讨论，培养1.展示具有权值的图。

2.提问：在这些生成树中，如何找到权值总和最小的那个？3.介绍常见的求最小生成树的算法，如Prim算法和Kruskal算法。

4.以具体示例讲解算法步骤。1.观察权值图，思考老师的问题。

2.尝试提出可能的方法。3.专注听讲，理解算法原理。

4.跟随老师的思路，在纸上模拟算法过程。1.引导学生思考最小生成树的概念；2.帮助学生掌握最小生成树的算法；知识点3：最短路径（30分钟）核心知识点：（1）最短路径的基本概念；（2）Dijkstra算法素质点：通过此部分知识培养学生逻辑思维能力、程序算法能力；通过讨论，培养1.以实际交通路线为例，引入最短路径的概念；

2.解释最短路径的含义和重要性；3.讲解Dijkstra算法等求最短路径的算法；

4.通过动画演示算法的执行过程；1.结合实际例子，理解最短路径的概念；

2.思考最短路径在生活中的应用场景；3.认真听讲，领会算法思想；

4.观察动画，清晰算法流程；1.使学生明确最短路径的实际意义；2.帮助学生理解最短路径算法；课中环节五总结（5分钟）总结：1.总结图的生成树、最小生成树和最短路径的重点内容；2.强调这些概念和算法在实际中的应用；3.布置课后学习任务；1.回顾所学内容，查漏补缺；2.思考如何将所学应用到实际问题中；强化学生对知识的掌握，培养应用意识。课后1.对课程内容进行复习，对易错点进行分类汇总；2.完成课后作业