17软件工程《数据结构与算法》 第10周安排

讲解第6章的内容 151-168页

重点

1、图的两种遍历:深度优先和广度优先

后面将要学习的生成树、拓扑排序等都是以遍历为核心的操作

2、图的存储结构:邻接表和邻接矩阵

3、最小生成树:Prim普里姆算法和Kruskal克鲁斯卡尔算法

实验内容于11月8日公布

大家可以根据自己的情况进行相应的预习

师说

哥尼斯堡七桥问题

1736年，年仅29岁的数学家欧拉来到普鲁士的古城哥尼斯堡（哲学家康德的故乡，今俄罗斯加里宁格勒）。普瑞格尔河正好从市中心流过，河中心有两座小岛，岛和两岸之间建筑有七座古桥。

欧拉发现当地居民有一项消遣活动，就是试图每座桥恰好走过一遍并回到原出发点，但从来没人成功过。

欧拉证明了这种走法是不可能的。现在看来，欧拉的证明过程非常简单，但他对七桥问题的抽象和论证思想，开创了一个新的学科:图论(Graph)。

https://blog.csdn.net/saltriver/article/details/54585595

欧拉的证明与其说是数学证明，还不如看作是一个逻辑证明。一个曾难住那么多人的问题，竟然是这样一个简单的出人意料的推理，还开创了一个新的学科。欧拉非常巧妙的把一个实际问题抽象成一个合适的数学模型，这种研究方法就是我们应该掌握的数学模型方法。这并不需要运用多么深奥的理论，但能想到这一点，却是解决问题的关键。