课程编排系统实战：基于有向图与拓扑排序的教学计划自动生成

1. 从课程依赖到有向图问题抽象与建模第一次接触教学计划编排问题时我被各种课程先修关系搞得晕头转向。比如学习《数据结构》前要先修《程序设计基础》而《操作系统》又依赖《数据结构》和《计算机组成原理》。这种复杂的依赖关系其实正是数据结构中**有向无环图DAG**的典型应用场景。把每门课程看作图中的一个顶点课程间的先修关系用有向边表示比如A→B表示B课程依赖A。这样构建出的有向图有个重要特性不允许出现环。想象如果《数据结构》依赖《操作系统》而《操作系统》又依赖《数据结构》学生就会陷入死循环永远无法毕业。实际编码时我们用邻接表存储这种关系typedef struct { char courseID[10]; // 课程编号 int credit; // 学分 int inDegree; // 入度统计依赖课程数 EdgeNode* firstEdge; // 邻接表指针 } CourseNode; typedef struct { CourseNode* courses; // 课程数组 int courseNum; // 课程总数 int maxTerm; // 最大学期数 int maxCredit; // 学期学分上限 } CurriculumGraph;在具体实现时我踩过一个坑没有及时更新节点的入度。比如删除某门课后忘记减少依赖该课程的节点入度导致后续拓扑排序出错。后来我增加了updateInDegree()函数专门处理这种情况void updateInDegree(CurriculumGraph* graph, int deletedCourse) { EdgeNode* edge graph-courses[deletedCourse].firstEdge; while (edge) { graph-courses[edge-adjacent].inDegree--; edge edge-next; } }2. 拓扑排序的魔法两种策略与四种实现拓扑排序就像课程安排的智能助手它能自动识别哪些课可以立即上哪些必须等前置课程完成。我常用的有两种经典算法2.1 卡恩算法Kahns Algorithm这个算法特别直观就像玩拆积木游戏每次只拿不依赖其他积木的块。具体步骤是找出当前入度为0的所有课程将这些课程加入教学计划移除这些课程并减少依赖它们的课程入度重复直到所有课程安排完毕void topologicalSort_Kahn(CurriculumGraph* graph, int* result) { int queue[MAX_COURSE], front 0, rear 0; // 初始化队列入度为0的课程 for (int i 0; i graph-courseNum; i) { if (graph-courses[i].inDegree 0) { queue[rear] i; } } int count 0; while (front ! rear) { int current queue[front]; result[count] current; // 加入结果序列 // 更新邻接课程入度 EdgeNode* edge graph-courses[current].firstEdge; while (edge) { int adj edge-adjacent; if (--graph-courses[adj].inDegree 0) { queue[rear] adj; } edge edge-next; } } if (count ! graph-courseNum) { printf(发现课程依赖环无法完成排课\n); } }2.2 基于DFS的算法深度优先算法则像探险家走迷宫沿着一条路径走到尽头然后回退记录路线。这种逆向思维得到的序列需要反转才是拓扑序void topologicalSort_DFS(CurriculumGraph* graph, int* result) { int stack[MAX_COURSE], top 0; bool visited[MAX_COURSE] {false}; for (int i 0; i graph-courseNum; i) { if (!visited[i]) { dfsVisit(graph, i, visited, stack, top); } } // 反转栈得到拓扑序 for (int i 0; i graph-courseNum; i) { result[i] stack[--top]; } } void dfsVisit(CurriculumGraph* graph, int course, bool* visited, int* stack, int* top) { visited[course] true; EdgeNode* edge graph-courses[course].firstEdge; while (edge) { if (!visited[edge-adjacent]) { dfsVisit(graph, edge-adjacent, visited, stack, top); } edge edge-next; } stack[(*top)] course; // 递归结束后入栈 }实际测试发现当课程数超过500门时DFS算法可能因递归过深导致栈溢出。这时可以改用显式栈实现非递归版本或者优先使用卡恩算法。3. 编排策略实战均匀分布 vs 尽早完成获得拓扑序列只是第一步真正的挑战是如何将课程分配到具体学期。我们开发了两种策略3.1 均匀分布策略目标是让每个学期的学分尽量均衡。算法步骤如下计算总学分和平均每学期学分按拓扑序逐个课程分配到当前学分最少的学期确保不超过学期学分上限void arrangeUniform(CurriculumGraph* graph, int* topoOrder, TermSchedule* terms) { int* termCredits calloc(graph-maxTerm, sizeof(int)); for (int i 0; i graph-courseNum; i) { int course topoOrder[i]; int targetTerm 0; // 找当前学分最少的学期 for (int t 1; t graph-maxTerm; t) { if (termCredits[t] termCredits[targetTerm]) { targetTerm t; } } // 检查学分上限 if (termCredits[targetTerm] graph-courses[course].credit graph-maxCredit) { addCourseToTerm(terms[targetTerm], course); termCredits[targetTerm] graph-courses[course].credit; } else { printf(无法在学期%d安排课程%s学分超限\n, targetTerm1, graph-courses[course].courseID); } } free(termCredits); }3.2 尽早完成策略目标是让课程尽可能集中在前几个学期。实现时需要按拓扑序逐个尝试将课程放入最早可能的学期检查该学期是否已包含其所有先修课程确保不超过学分上限void arrangeEarly(CurriculumGraph* graph, int* topoOrder, TermSchedule* terms) { for (int i 0; i graph-courseNum; i) { int course topoOrder[i]; int earliestTerm 0; // 找出所有先修课程所在的最晚学期 EdgeNode* edge graph-courses[course].firstEdge; while (edge) { int preTerm findCourseTerm(terms, graph-maxTerm, edge-adjacent); if (preTerm earliestTerm) { earliestTerm preTerm 1; } edge edge-next; } // 从最早可能学期开始尝试 for (int t earliestTerm; t graph-maxTerm; t) { if (terms[t].totalCredit graph-courses[course].credit graph-maxCredit) { addCourseToTerm(terms[t], course); break; } } } }实测发现计算机专业12门核心课程总学分42在6个学期内安排时两种策略差异明显均匀分布每学期7学分左右课程数3-4门尽早完成前3个学期平均10学分后3个学期平均4学分4. 系统实现中的工程挑战4.1 数据持久化设计我们采用文本文件存储课程数据格式如下6 10 12 // 学期数,学分上限,课程数 C01 2 // 课程号 学分 C02 3 C01 // 课程号 学分 先修课程 C03 4 C01 C02 ...文件读取模块需要处理多种异常情况CurriculumGraph* loadCurriculum(const char* filename) { FILE* file fopen(filename, r); if (!file) { perror(无法打开课程文件); return NULL; } CurriculumGraph* graph malloc(sizeof(CurriculumGraph)); // 读取基础参数 if (fscanf(file, %d %d %d, graph-maxTerm, graph-maxCredit, graph-courseNum) ! 3) { // 错误处理... } // 分配课程数组内存 graph-courses calloc(graph-courseNum, sizeof(CourseNode)); char line[256]; fgets(line, sizeof(line), file); // 跳过第一行 for (int i 0; i graph-courseNum; i) { if (!fgets(line, sizeof(line), file)) { // 错误处理... } char* token strtok(line, ); strncpy(graph-courses[i].courseID, token, sizeof(graph-courses[i].courseID)); token strtok(NULL, ); graph-courses[i].credit atoi(token); // 处理先修课程 while ((token strtok(NULL, )) ! NULL) { int preCourse findCourseIndex(graph, token); if (preCourse 0) { addEdge(graph, preCourse, i); // 添加边 graph-courses[i].inDegree; // 增加入度 } } } fclose(file); return graph; }4.2 用户交互设计我们开发了简单的控制台菜单void showMainMenu() { printf(\n 教学计划编排系统 \n); printf(1. 查看课程信息\n); printf(2. 修改课程参数\n); printf(3. 均匀分布策略排课\n); printf(4. 尽早完成策略排课\n); printf(5. 导出教学计划\n); printf(0. 退出\n); printf(请选择: ); } void handleUserChoice(CurriculumGraph* graph) { int choice; scanf(%d, choice); switch (choice) { case 1: showCourses(graph); break; case 2: modifyParameters(graph); break; case 3: { int order[MAX_COURSE]; topologicalSort_Kahn(graph, order); arrangeUniform(graph, order, termSchedules); break; } // 其他case处理... } }4.3 性能优化技巧当课程规模增大时如全校课程体系需要优化算法效率优先队列优化使用堆来快速获取入度为0的节点// 使用最小堆管理入度为0的节点 void initZeroInDegreeQueue(CurriculumGraph* graph, PriorityQueue* queue) { for (int i 0; i graph-courseNum; i) { if (graph-courses[i].inDegree 0) { push(queue, i); } } }并行拓扑排序对独立子图进行并行处理增量更新当修改少量课程时只重新计算受影响的部分在Intel i7处理器上测试优化后的算法处理1000门课程仅需约50ms完全满足实时交互需求。