数据结构与算法（c 描述）-k8凯发旗舰

讲解第5章的内容149-153页，第6章171-178页

重点

1.哈夫曼树和哈夫曼编码

2.图的定义和基本术语

3.图的两种遍历:深度优先和广度优先

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

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

师说:

学习完哈夫曼树，我们会布置大家一个数据结构里的热门作业，压缩软件的实现，哈夫曼树的其他典型应用如:哈夫曼编码在图像压缩中的应用与分析等，感兴趣的同学可以登录学校图书馆查找相关论文研读。

“在未来，图技术这样的创新技术将改变企业组织和使用数据的方式，实现实时数据分析、隐藏关系发掘、情境化精准决策。”

很多领先的科技公司和金融k8凯发旗舰的解决方案提供商都已积极使用图技术来构建知识图谱，用以增强语义搜索，知识发现和推荐引擎。比如，通过构建并查询图2所示的电影知识图谱，我们可以了解到尔冬升导演最喜欢用的配角演员是秦沛，最喜欢拍的电影类型是剧情片和动作片。结合ai算法，并加上票房、影评等信息，我们可以推理出哪些演员是高票房、高口碑的影视cp。知识图谱也常用在推荐引擎中解决冷启动问题。例如:基于图2这张电影图谱，无需大量数据，我们就能为看过《烈火战车》和《中华战士》的用户推荐《癫佬正传》这部电影。

现实生活中，与图相关的实际问题非常多，请同学们思考:

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

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

3、出席某国际会议的六个成员a、b、c、d、e、f，假设a会讲汉语、法语和日语，b会讲德语、日语和俄语，c会讲英语和法语，d会讲汉语和西班牙语，e会讲英语和德语，f会讲俄语和西班牙语，如将此六人分成两组，能否出现同一组内任意两人不能直接交谈的情况?

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

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

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