拓扑排序算法对排课方案判定的应用

《拓扑排序算法对排课方案判定的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、拓扑排序算法对排课方案判定的应用在日常生活中,常用图来表示一些问题或概念,如IC设计、城市间交通道路规划、作业调度等。图和树一样,也是一种非线性数据结构。图和树的最大差异在于:树描述的是数据元素(结点)之间的层次关系,每一层上的数据元素可能和下一层中多个元素(即孩子结点)相关,但只能和上一层中一个元素相关,而图结构研究两顶点之间是否相连的关系,在图中,结点之间的关系是任意的,图中任意两个数据元素之间都有可能相关。图结构提供了简单的方式来描述一个问题、系统或状况等。这种图的先后顺序关系便是我们所提到的拓扑图,我们所要做的事情就是从这些拓扑图里面提取

2、出符合实际生产需要的拓扑序列,以达到解决实际问题的需要。然而,基于有向图的拓扑排序在哪些方面有应用呢?我们都知道一个复杂的工程通常可以分解成一组小任务的集合,完成这些小任务意味着整个工程的完成。例如,汽车装配工程可分解为以下任务:将底盘放上装配线,装轴,将座位装在底盘上,上漆,装刹车,装门等等。任务之间具有先后关系,例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动(ActivityOnVertex,AOV)X络。再例如,一个建筑工程的过程,通过对我们上面的分析,可以用拓扑图表示为如下所示,我们可能要问:该项工程或

3、系统能否顺利完成?如果一个工程队在一个时段只能做一件活动,应该按什么顺序完成这些活动?还有,比如我们现在的排课问题,也其实是一个拓扑有效序列的求解过程,在此类问题中,课程我们可以用向图中的结点来表示,然后课程之间的先后关系,我们可以用图的弧来表示,弧头是弧尾所指的结点的后导课程,弧尾是弧头的前驱课程。按照此种定义,我们从中提取出一个课程相互关系的结点元素的序列,便是我们所要求解的拓扑序列。1排课问题的描述每个学期,我们都要对不同的课程进行排课,然而,课程之间有着特殊的制约性质,我们还得考虑,比如计算机核心课程里面的数据结构的前导课程是计算机文化基

4、础,因此各个课程之间都有着严格的前后约束关系。其次,我们假设每个学生选课的情况是一个时间段只能选取一门课程,而且前后的几个时间段必须是严格的连续的关系。再次,各个时间段选取的课程不能是以前已经选取过的课程,在这里我们为了简单起见,假设选取的时间段为一个学期。最后,我们从建模后的拓扑图中提取出一个拓扑序列作为一个学生的各个学期的选课顺序。综上所述,该条件下排课问题的建模如下:1)各个课程之间有着严格的先后顺序关系。2)两个相邻课程之间的跨度为一个时间段,具体就是一个学期。3)每个学生每个学期只能选一门课程。4)选择一个拓扑序列便是一个学生的各个学期

5、的选课情况序列。2有向图的存储结构设计以及堆栈的定义2.1有向图的定义与解释有向图是一个二元组,其中:1)V是非空集合,称为顶点集。2)E是V×V的子集,称为边集。直观来说,若图中的每条边都是有方向的,则称为有向图。有向图中的边是由两个顶点组成的有序对,有序对通常用尖括号表示,如表示一条有向边,其中vi是边的始点,vj是边的终点。和代表两条不同的有向边。2.2邻接矩阵邻接矩阵(AdjacencyMatrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:1)无

6、向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。因此,用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵;对有n个顶点的无向图则只存入上(下)三角阵中剔除了左上右下对角线上的0元素后剩余的元素,故只需12...(n-1)=n(n-1)/2个单元。2)无向图邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度。3)有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度,第i列非零元素的个数为第i个顶点的入度,第i个顶点的度为第i行与第i列非零元素个数之和。4)用邻接矩阵表示图,很容易确定图中任意两个顶点是否有

7、边相连。2.3邻接表邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点。又称链接表。其中:1)在有向图的邻接表中不易找到指向该顶点的弧2)在有向图的邻接表中,对每个顶点,链接的是指向该顶点的弧。对于有向图,vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此,将有向图的邻接表称为出边表。邻接表的形式说明如下:typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域//若要表示边上的权,则应增加

8、一个数据域}EdgeNode;typedefstructvnode{//顶点表结点VertexTypevertex;//顶点域EdgeN