1．、理解重点词语。4．有感情地朗读课文。教学重点：教学难点：授课内容5.6 有向无环图及其应用5.6.1 拓扑排序有向无环图可以用来描述一项工程或任务的进行过程。 在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：① 先后关系，即必须在一子项目完毕后，才能开始实行另一个子项目；② 子项目之间无顺序规定，即两个子项目可以同时进行，互不影响。 实际问题： 一个表达偏序的有向图可用来表达一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或是一个数据流图(每个顶点表达一个过程)。图中每一条有向边表达两个子工程之间的顺序关系(领先关系)。在工厂中，一件设备的生产涉及许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些第一章绪论第二讲 算法和算法分析课程必须在一些课程学完后才能开始学。 这些类似的问题都可以用有向图来表达，我们把这些子项目、工序、课程当作一个个顶点称之为活动(Activity)。假如从顶点 Vi 到 Vj 之间存在有向边< Vi，Vj>,则表达活动 i 必须先于活动 j 进行。这种图称做顶点表达活动的网络(Activity On Vertex network,简称 AOV 网络)。 例如，一个软件专业的学生必须学习一系列基本课程(如图 7.26 所示)，其中有些课程是基础课，它独立于其它课程，如《高等数学》；而另一些课程必须在学完作为它的基础的先修课程才能开始。如在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表达，如图 7.27 所示。图中顶点表达课程，有向边(弧)表达先决条件。若课程i 是课程 j 的先决条件，则图中有弧 。 建立模型： 这种用顶点表达活动，用弧表达活动间的优先关系的有向图称为顶点表达活动的网 (Activity On Vertex Network)，简称 AOV-网。在网中，若从顶点 i 到顶点 j 有一条有向途径，则 i 是 j 的前驱；j 是 i 的后继。若是网中一条弧，则 i 是 j 的直接前驱；j 是 i 的直接后继。注意： 在 AOV-网中不应当出现有向环，由于存在环意味着某项活动应以自己为先决条件。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表白存在一个死循环。因此，对给定的 AOV-网应一方面鉴定网中是否...
