多7章离广义表
1
图( Graph)是一种较线性表和树更为复杂的数据结构。在 线性表中,数据元素之间仅有线性关系,即每个数据元素只有 个直接前驱和一个直接后继;在树形结构中,数据元素之间 有着明显的层次关系,虽然每一层上的数据元素可能和下一层 中多个元素(孩子)相关,但只能和上一层中一个元素(双亲 相关;而在图形结构中,结点之间的关系可以是任意的,任意 两个数据元素之间都可能相关。 图在各个领域都有着广泛的应用如电路网络分析、交通运输 管理与线路的铺设、印刷电路板与集成电路的布线等众多直接 与图有关的问题,它们必须用图的有关方法进行处理;另外像 工作的分配、工程进度的安排、课程表的制订、关系数据库的 设计等许多实际问题,如果间接地用图来表示,处理起来比较 方便。这些技术领域都是把图作为解决问题的主要数学手段来 使用,因此,如何在计算机中表示和处理图结构,就是计算机 科学需研究的一项重要课题
2
【学习国标】 1.领会图的类型定义 2.熟悉图的各种存储结构及其构造算法 了解各种存储结构的特点和选用原则 3.熟练掌握图的两种遍历算法 4.理解各种图的应用问题的算法 5了解广义表的结构和使用
3
【重点和点】 图的应用极为广泛,而且图的各种应用问 题的算法都比较经典,因此本章重点在于 理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度 优先搜索遍历和图的广度优先搜索遍历 无向网的最小生成树、最短路径、拓扑排 序、关键路径
4
第七章习题 基础知识 -P47:717.5777.97107.11 °作业 P49:7227.237.247287.32 P50:7.367.41
5