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

摘要:排课问题是现在各个学校必须面临的一个问题。而且随着近年来学生规模的扩招,教育机构的复杂化,课程各类的多样化,排课的问题越来越难。尽管目前对排课采用了程序设计的计算机智能排课系统,但是仍然存在着这样或者那样的问题。最为突出的一个问题,比如,有一些排课方案,看上去完美无缺,或者效率比较高,甚至达到了最优解,但是具体地去实施的时候,发现整个课程的设计方案有着大的漏洞,经常出现的问题是,排课的拓扑图出现了一些环,以至于进入了死循环。该文的目的就是针对于如何检测环的存在而避免错误的排课方案。本文采用的算法是基于拓扑序列的拓扑排序算法对特定条件的排课问题提出的一种解决方案,具体的实验结果是展示出一个符合条件的课程拓扑序列,整个算法的设计与实现过程将要用到邻接表,堆栈等数据结构等等。

关键词:有向图,拓扑排序,排课

中图分类号:TP312文献标识码:A文章编号:1009-3044(2010)16-4587-03

Topological Sorting Algorithm to Determine the Application Arranging Program

ZHU Jun-jun

(College of Computer Science, Sichuan Normal University, Chengdu 610101, China)

Abstract: Course Scheduling problem is a problem that all schools must to face. recently students along with the size of enrollment, educational institutions, complicated courses of various types of diversity, curriculum arrangement is increasingly difficult. Although use of the programming based on AI design, there are still so many problems. The most prominent problem, such as, some course arrangement program, looks perfect apparently, or more efficient, even to the best optimal solution, but when it is putting in using, it is found that the design of the course has a major mistake. Because there are some rings in the schedule, so the program drops into the dead cycle. The purpose of this paper is aimed at how to detect the presence of Central Timetabling program to avoid mistake schedules. In this paper, the algorithm is based on the topological sequence of topological sorting algorithm on specific conditions, course arrangement proposed a solution, the specific results that demonstrate the topology of a sequence of courses which meet with the requirements, the design and implementation of the algorithm will use the data structure of adjacent table, stack, etc.

Key words: directed graph; topological sorting; course arranging

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

然而,基于有向图的拓扑排序在哪些方面有应用呢?我们都知道一个复杂的工程通常可以分解成一组小任务的集合,完成这些小任务意味着整个工程的完成。例如,汽车装配工程可分解为以下任务:将底盘放上装配线,装轴,将座位装在底盘上,上漆,装刹车,装门等等。任务之间具有先后关系,例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示――称为顶点活动( Activity On Vertex, AOV)网络。再例如,一个建筑工程的过程,通过对我们上面的分析,可以用拓扑图表示为如下所示,我们可能要问:该项工程或系统能否顺利完成?如果一个工程队在一个时段只能做一件活动,应该按什么顺序完成这些活动?还有,比如我们现在的排课问题,也其实是一个拓扑有效序列的求解过程,在此类问题中,课程我们可以用向图中的结点来表示,然后课程之间的先后关系,我们可以用图的弧来表示,弧头是弧尾所指的结点的后导课程,弧尾是弧头的前驱课程。按照此种定义,我们从中提取出一个课程相互关系的结点元素的序列,便是我们所要求解的拓扑序列。

1 排课问题的描述

每个学期,我们都要对不同的课程进行排课,然而,课程之间有着特殊的制约性质,我们还得考虑,比如计算机核心课程里面的数据结构的前导课程是计算机文化基础,因此各个课程之间都有着严格的前后约束关系。其次,我们假设每个学生选课的情况是一个时间段只能选取一门课程,而且前后的几个时间段必须是严格的连续的关系。再次,各个时间段选取的课程不能是以前已经选取过的课程,在这里我们为了简单起见,假设选取的时间段为一个学期。最后,我们从建模后的拓扑图中提取出一个拓扑序列作为一个学生的各个学期的选课顺序。综上所述,该条件下排课问题的建模如下:

1) 各个课程之间有着严格的先后顺序关系。

2) 两个相邻课程之间的跨度为一个时间段,具体就是一个学期。

3) 每个学生每个学期只能选一门课程。

4) 选择一个拓扑序列便是一个学生的各个学期的选课情况序列。

2有向图的存储结构设计以及堆栈的定义

2.1 有向图的定义与解释

有向图是一个二元组,其中:

1) V是非空集合,称为顶点集。

2) E是V×V的子集,称为边集。

直观来说,若图中的每条边都是有方向的,则称为有向图。有向图中的边是由两个顶点组成的有序对,有序对通常用尖括号表示,如表示一条有向边,其中vi是边的始点,vj是边的终点。和代表两条不同的有向边。

2.2 邻接矩阵

邻接矩阵(Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:

1) 无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。因此,用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵;对有n个顶点的无向图则只存入上(下)三角阵中剔除了左上右下对角线上的0元素后剩余的元素,故只需1+2+...+(n-1)=n(n-1)/2个单元。

2) 无向图邻接矩阵的第i行(或第i列)非零元素的个数正好是第i个顶点的度。

3) 有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度,第i列非零元素的个数为第i个顶点的入度,第i个顶点的度为第i行与第i列非零元素个数之和。

4) 用邻接矩阵表示图,很容易确定图中任意两个顶点是否有边相连。

2.3 邻接表

邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点。又称链接表。其中:

1) 在有向图的邻接表中不易找到指向该顶点的弧

2) 在有向图的邻接表中,对每个顶点,链接的是指向该顶点的弧。

对于有向图,vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此,将有向图的邻接表称为出边表。邻接表的形式说明如下:

typedef struct node{//边表结点

int adjvex; //邻接点域

struct node *next; //链域

//若要表示边上的权,则应增加一个数据域

}EdgeNode;

typedef struct vnode{ //顶点表结点

VertexType vertex; //顶点域

EdgeNode *firstedge;//边表头指针

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];//AdjList是邻接表类型

typedef struct{

AdjList adjlist;//邻接表

int n,e; 图中当前顶点数和边数

}ALGraph; //对于简单的应用,无须定义此类型,可直接使用AdjList类型。

在本文中将采用的储存结构便是邻接表,至于为什么要采用邻接表而不采用邻接矩阵,我们将在后面予以分析。

2.4 堆栈的定义以及堆栈在本文中的作用

堆栈是一个不容忽视的概念,但是很多人甚至是计算机专业的人也没有明确堆栈其实是两种数据结构。堆栈都是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。要点:堆:顺序随意栈:后进先出(Last-In/First-Out)。

在本文中为了快速有效地输出拓扑序列,应该要对待输出的结点进行暂存,并且由于后面待输出的结点需要与前面已经输出的结点发生联系,因此,如果采用数组或者其它的数据结构存储便会比较麻烦,在这里我们综合考虑到堆栈的特质,我们采用堆栈作为待输出结点的缓冲区域。

3 拓扑排序算法的描述

3.1 拓扑排序算法思路

1) 在图中找一个没有前驱的顶点,并把它输出;

2) 从图中删除该顶点及由它发出的弧;

3) 重复第1、2步,直到所有顶点都输出(顶点输出序列为拓扑序列)或剩余顶点中找不到没有前驱的顶点(图中存在回路)。

3.2 拓扑排序伪代码

1) 计算每个顶点的入度indegree[];

2) 栈S初始化;计数器count初始化;

3) 扫描顶点表,将入度为零的顶点入栈;

4) 当栈S非空时反复循环:

step 3.1 弹出栈顶元素i;打印i;count加1;

step3.2 将顶点i的各个邻接点的入度减1;

step3.3 将新的入度为0的顶点入栈;

5) if (count

3.3 拓扑排序算法程序代码

Status ToplogicalSort(ALGraph G){

FindIndegree(G,indegree);

InitStack(S);

for( i=1;i

if (!indegree[i]) Push(S,i);

count=0;

while (!StackEmpty(S)){

Pop(S,i);printf(i,G.vertices[i].data);++count;

for(p=G.vertices[i].firstarc;p;p=p->nextarc){

k=p->adjvex;

if (- -indegree[k]) Push(S,k);

}//for

}//while

if (count

else return OK;

}//ToplogicalSort

4 实例分析

4.1 排课问题的数学建模

如表1所示,各个课程号代表的含义,以及各个课程相对应的先修课。

如图1表示了各个课程之间的拓扑图,其中结点表示课程,弧代表前后两门课程之间的约束关系。

4.2 实验模拟初始状态下各个结点的入度统计与邻接表的状态

图2为各个顶点的入度统计图;图3为初始状态下邻接表的状态。

5 实验结果及分析

5.1 实验结果

运行的结果表明,本课程安排不存在回路,因此是一个恰当有效的课程安排方案。并且可以产生多种拓扑排序的序列供学生选课方案进行选择,例如可以是:

1) A,B,C,D,E,F,G

2) A,C,B,D,F,E,G

3) A,C,B,D,E,F,G

5.2 算法复杂度分析

由于本算法采用了一个一阶的循环,因此循环体内的语句将执行N个单位次数,另外由于使用了堆栈作为数据暂存结构,则复杂系数为E,因此整个算法的时间复杂度是:O(N+E)。

5.3 思考

在本文的算法里面,对于待输出的结点是采用堆栈作为暂存,而堆栈最大的特点是“先进先出”,但是本算法里面根本没有运用到堆栈的这个性质,而仅仅是用来作为数据的暂时存储,这里我们其实也可以采用队列的方法。

另外,我们也完全可心采用邻接矩阵的方式对有向图进行存储,而不一定是采用邻接表进行存储。但是由于在求解每个结点的入度的时候,我们需要扫描整个邻接矩阵的一行或者一列,而对于N个结点,则需要扫描N*N次,因此时间复杂度则为O(N*N),因此,采用邻接表的效率要高一些。

参考文献:

[1] 严蔚敏,吴伟民.数据结构C语言版[M].北京:清华大学出版社,2007.

[2] 维斯.数据结构与算法分析C语言描述[M .北京:机械工业出版社,2004.

[3] 周建丽,黄志真.用拓扑排序安排课程顺序[J].重庆交通学院学报,1997(4).

[4] 刘声田,路明.面向对象技术获取AOV网络拓扑序列的算法[J].山东电大学报,2005(2).