您申请加入课程:数据结构与算法(C++描述)
需要验证您的身份,请输入课程密码:
您的学号:
班级选择:
课程密码:
  • 创建者

    Creator

    潘家辉
  • 活跃度

    Activeness

  • 访问量

    Visits

    212799

教学公告

18软工 第10周安排
[作者: 潘家辉  发布时间:2019-11-04 06:21:11  浏览次数:819次]

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


讲解第6章的内容 171-187页


重点:

1、图的定义和基本术语

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

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

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


实验内容于11月5日公布

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


师说

哥尼斯堡七桥问题

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

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

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


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


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


现实生活中,与图相关的实际问题非常多:


1、七巧板涂色问题,使用至多 4 种不同颜色对七巧板涂色,要求每个区域涂一种颜色,相邻区域的颜色互不相同。求涂色方案。


2、某公司生产若干种化学制品,其中有些制品如果放在一起可能产生化学反应,因此公司必须将仓库分成相互隔离的若干区,请设计合理的仓库分区。


3、出席某国际会议的六个成员A、B、C、D、E、F,假设A会讲汉语、法语和日语,B会讲德语、日语和俄语,C会讲英语和法语,D会讲汉语和西班牙语,E会讲英语和德语,F会讲俄语和西班牙语,如将此六人分成两组,能否出现同一组内任意两人不能直接交谈的情况?


4、农夫过河问题。一个农夫带着一只狼、一只羊和一筐菜,想从河一边(左岸)乘船到另一边(右岸),由于船太小,农夫每次只能带一样东西过河,但是如果没有农夫看管,则狼会吃羊,羊会吃菜。其给出过河方案。


5、已知软件工程专业专业的核心课程,编制合适的教学计划。


6、旅游出行的路径问题......



相关课程

扫一扫二维码,快速加入本课程!

放大二维码 查看使用方法
关闭