武汉软件工程职业学院《数据结构讲义》第02讲 算法和算法分析

《武汉软件工程职业学院《数据结构讲义》第02讲 算法和算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二讲算法和算法分析第一章绪论1．、理解重点词语。4．有感情地朗读课文。Ø教学重点：Ø教学难点：Ø授课内容5.6有向无环图及其应用5.6.1拓扑排序有向无环图可以用来描述一项工程或任务的进行过程。在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。 实际问题：    一个表示偏序的有向图可用来表示一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或是一个数据流图(每个顶点表示一个过程)。图中每一条有向边表示

2、两个子工程之间的次序关系(领先关系)。在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(ActivityOnVertexnetwork,简称AOV网络)。    例如，一个软件专业的学生必须学习一系列基本课程(如图

3、7.26所示)，其中有些课程是基础课，它独立于其它课程，如《高等数学》；而另一些课程必须在学完作为它的基础的先修课程才能开始。如在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示，如图7.27所示。图中顶点表示课程，有向边(弧)表示先决条件。若课程i是课程j的先决条件，则图中有弧。    建立模型：    这种用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(ActivityOnVertexNetwork)，简称AOV-网。在网中，若从顶点i到

4、顶点j有一条有向路径，则i是j的前驱；j是i的后继。若是网中一条弧，则i是j的直接前驱；j是i的直接后继。注意：    在AOV-网中不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的AOV-网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。【例如】表5-6-1是某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如图5-6-1所示。   表5-6-1某

5、专业课程设置 图5-6-1（a）AOV网络在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。AOV网络中一定不能有有向环路。例如在图5-6-1（b）那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得

6、到满足。由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。如何进行拓扑排序?    解决方案：        解决的方法很简单：拓扑排序方法(1)在AOV网中选择一个没有前驱（即入度为0）的顶点，并把它输出；(2)从网络中删去该顶点和从该顶点发出的所有有向边；(3)重复执行上述两步，直到网中所有的顶点都被输出(此时，原AOV网络中的所有顶点和边就都被删除掉了)。如果进行到某一

7、步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。（a）（b）（c）（d）（e）（f）图5-6-2AOV网及拓扑序列的产生过程其中：（a）AOV网；(b)输出v0后；（c）输出v5后；（d）输出v3后；（e）输出v2后；（f）输出v1后。这样得到的一个拓扑排序序列为：v0,v5,v3,v2,v1,v4如何在计算机中实现?为了实现拓扑排序，针对上述两个步骤，采用邻接表作为有向图的存储结构，并且在表结点中增设一个入度，存放顶点的入度。例如图5-6-2种的AOV网的邻接表如图5-6-3（a）所示。这样，入度域为