17 数据与结构(图结构)逐字稿 高中 · 信息技术 · 教科版 · 必修1 数据与计算

admin312024-01-04 09:54:01

老师

同学们好,欢迎来到江苏省名师空中课堂,那在这一课时我们将要学习数据与结构的第三小节,那在这一刻时,我们会使用一个案例,也就是取快递的最短路径,来综合运用我们之前所学的知识。取快递对于每个人在现代生活中都是非常熟悉的一个环节,那我们现在假设自己就是这个人。然后今天我们收到了很多的快递信息,但是有一个问题,我们收到的不同快递,它们分布在了不同的快递门店,那右边这张表格列出了每两个地点当中需要花费的时间。现在我们需要想达到一个目标,就是使用最短的时间取到所有的快递,然后回到家中。

老师

请同学们自己动动脑筋想想,我们怎么可以求出来这一个最短时间的路径?答案,你算出来了吗?这道题的答案是从家出发,然后经过 a C、b,然后再回到家,或者是把这个顺序颠倒过来,从家出发,先去b,然后去c,然后a,最后回到家。那我们这个答案是怎么算出来的?我们看一下运用到我们之前所学的数据结构的抽象的思想。我们可以把家以及快递门店抽象为一个顶点,然后把每个位置当中的线路抽象为一条边,那所花的时间就可以抽象为边上的权重。于是我们得到了这样的一张图,这张图是不是就变得熟悉了?就是我们上一课时所讲的图结构。

老师

那么接下来我们要如何求得取快递的最短路线,我们要列出每一种可能性,也就是从家出发。每一种可以走的路径我们都需要列出来。当列出来之后,以第一条路径为例,从家出发,然后走到a,走到b,走到c,最后回到家。然后我们编的权重可以把它写在树的枝上面,最后相加,可以得到每一种可能性所花费的时间。经过比较,我们找到了最短的路径所花费的时间,这里是 17 分钟,相应的它的逆序的路径也是 17 分钟。那从这个解决的办法中我们可以看到图的问题可以转化为数来求解。那接下来我们要用一个 Python 的代码去实现这个过程,请同学们先在 Python 中运行这个求最短路径的代码,然后去观察运行的结果。运行出来之后,我们要尝试去读懂代码。

老师

首先我们先来看这个程序的主程序部分。先看第 12 行,就是用字典来表示了刚才那张图的所有顶点边以及权重。大家可以回顾一下字典的表示方法是键值对的表示方法,用键来表示一个顶点,然后再嵌套一个字典来表示与它相连相连的顶点,相连顶点的权重表示为值,也就是在冒号的后面,如果一个顶点与许多的顶点相连接,我们就可以用逗号把它们键值对给分隔开来。最后就得到了第 12 行这样的表

查看隐藏内容
《17 数据与结构(图结构)逐字稿 高中 · 信息技术 · 教科版 · 必修1 数据与计算》.doc
将本文下载保存,方便收藏和打印
导出文档