数据结构与算法(c 描述)-z6尊龙旗舰厅
|
|
|
教学公告
18软件工程《数据结构与算法》 第10周安排
讲解第6章的内容 171-187页
重点:
1、图的定义和基本术语
2、图的两种遍历:深度优先和广度优先
后面将要学习的生成树、拓扑排序等都是以遍历为核心的操作
3、图的存储结构:邻接表和邻接矩阵
实验内容于11月5日公布
大家可以根据自己的情况进行相应的预习
师说
1736年,年仅29岁的数学家欧拉来到普鲁士的古城哥尼斯堡(哲学家康德的故乡,今俄罗斯加里宁格勒)。普瑞格尔河正好从市中心流过,河中心有两座小岛,岛和两岸之间建筑有七座古桥。
欧拉发现当地居民有一项消遣活动,就是试图每座桥恰好走过一遍并回到原出发点,但从来没人成功过。
欧拉证明了这种走法是不可能的。现在看来,欧拉的证明过程非常简单,但他对七桥问题的抽象和论证思想,开创了一个新的学科:图论(graph)。
欧拉的证明与其说是数学证明,还不如看作是一个逻辑证明。一个曾难住那么多人的问题,竟然是这样一个简单的出人意料的推理,还开创了一个新的学科。欧拉非常巧妙的把一个实际问题抽象成一个合适的数学模型,这种研究方法就是我们应该掌握的数学模型方法。这并不需要运用多么深奥的理论,但能想到这一点,却是解决问题的关键。
现实生活中,与图相关的实际问题非常多:
1、七巧板涂色问题,使用至多 4 种不同颜色对七巧板涂色,要求每个区域涂一种颜色,相邻区域的颜色互不相同。求涂色方案。
2、某公司生产若干种化学制品,其中有些制品如果放在一起可能产生化学反应,因此公司必须将仓库分成相互隔离的若干区,请设计合理的仓库分区。
3、出席某国际会议的六个成员a、b、c、d、e、f,假设a会讲汉语、法语和日语,b会讲德语、日语和俄语,c会讲英语和法语,d会讲汉语和西班牙语,e会讲英语和德语,f会讲俄语和西班牙语,如将此六人分成两组,能否出现同一组内任意两人不能直接交谈的情况?
4、农夫过河问题。一个农夫带着一只狼、一只羊和一筐菜,想从河一边(左岸)乘船到另一边(右岸),由于船太小,农夫每次只能带一样东西过河,但是如果没有农夫看管,则狼会吃羊,羊会吃菜。其给出过河方案。
5、已知软件工程专业专业的核心课程,编制合适的教学计划。
6、旅游出行的路径问题......