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 卡恩算法（Kahn's Algorithm）

这个算法特别直观，就像玩拆积木游戏：每次只拿不依赖其他积木的块。具体步骤是：

1. 找出当前入度为0的所有课程
2. 将这些课程加入教学计划
3. 移除这些课程，并减少依赖它们的课程入度
4. 重复直到所有课程安排完毕

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 均匀分布策略

目标是让每个学期的学分尽量均衡。算法步骤如下：

1. 计算总学分和平均每学期学分
2. 按拓扑序逐个课程分配到当前学分最少的学期
3. 确保不超过学期学分上限

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", targetTerm+1, graph->courses[course].courseID); } } free(termCredits); }

3.2 尽早完成策略

目标是让课程尽可能集中在前几个学期。实现时需要：

1. 按拓扑序逐个尝试将课程放入最早可能的学期
2. 检查该学期是否已包含其所有先修课程
3. 确保不超过学分上限

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 性能优化技巧

当课程规模增大时（如全校课程体系），需要优化算法效率：

1. 优先队列优化：使用堆来快速获取入度为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); } } }

2. 并行拓扑排序：对独立子图进行并行处理
3. 增量更新：当修改少量课程时，只重新计算受影响的部分

在Intel i7处理器上测试，优化后的算法处理1000门课程仅需约50ms，完全满足实时交互需求。