AOV网拓扑排序实现31门课程教学计划编制

简介：围绕教学计划编制问题，这份压缩包面向学习数据结构与图论、需要完成课程安排建模或课程设计的学生与教师，重点解决课程先修关系下的合理排序问题。资源以1个doc文档承载论文与源程序，压缩包约190KB，内容将31门计算机课程抽象为AOV网，用邻接表描述入度与边表，并比较深度优先与广度优先拓扑排序在并行课程安排上的差异，说明为何采用BFS逐层推进。文档还给出初始化图、空队列创建、判空、入队、出队、取队首及拓扑排序等函数设计，并讨论学分、周课时与学期负担均衡等实际调整。已有297人学习，适合用来理解从问题抽象、数据结构选型到算法实现的完整过程，也可作为实验报告、课程论文和源程序对照参考。

1. 教学计划编制不是排课表：31 门课的先修关系怎么变成一条可执行序列

教务系统里点几下鼠标排出来的东西叫课表，而教学计划编制解决的是更底层的问题——哪门课必须先学、哪几门课可以并着学、一条满足全部先修约束的学习序列到底长什么样。这份资源围绕这件事给了两样东西：一篇把思路讲透的论文，和一份能直接编译运行的 C 源程序。它把 31 门计算机专业课建成一张 AOV 网（有向无环图），顶点是课程，边是「学完 A 才能学 B」的依赖，用邻接表存依赖、链式队列跑广度优先拓扑排序，最后输出一条合法序列。正在做数据结构课设、需要一份既能跑通又能讲清原理的代码的同学，拿过去改改课程表就能用；想找个三十来个顶点、四十多条边的真实规模图练手拓扑排序的开发者，也能从里面看到几个挺典型的翻车点。

2. 存储设计拆解：邻接表、入度数组和链式队列如何撑起一个 AOV 网

课程依赖图有两个特点决定了存储方案：顶点数固定且不大（31 个），但每个顶点的出边数量差别巨大——「高等数学」后面挂着数值分析、计算机图形学，而「电子商务」只有一条出边指向网络数据库编程。用邻接矩阵要开 31×31 的二维数组，绝大部分格子是空的；用邻接表只存真实存在的边，遍历后继时也不用扫描 31 个位置。源程序选的是邻接表，配套一个链式队列做 BFS 的驱动结构。

2.1 三层结构体：顶点、边表结点、图的外壳

先把图拆成三个层次来看：边表结点只关心「指向谁」和「下一条边在哪」，顶点结点除了编号和出边链表头，还额外挂了一个inDegree字段，把入度这种运行时才能算出来的信息直接内嵌在顶点上，避免再开一个平行数组；最外层graphList用一个定长指针数组装 31 个顶点，加一个n记录顶点总数。

struct edgeNode { int index; /* 这条边指向的顶点编号，从 1 开始 */ pEdgeNode next; /* 同一个顶点的下一条出边 */ }; struct vertexNode { int vertexInfo; /* 课程编号，1..31 */ int inDegree; /* 该课程当前还有几门先修课没排进去 */ pEdgeList next; /* 出边链表头 */ }; struct graphList { int n; /* 顶点总数 */ pVertexNode vertex[31]; /* 定长指针数组，下标 0..30 对应课程 1..31 */ };

这里有两个约定值得记住，后面几乎所有坑都跟它们有关。第一个是「课程编号从 1 开始，数组下标从 0 开始」，所以任何vertexInfo拿去索引数组时都要减一，inDegree累加时也要减一，漏掉一次结果就全歪。第二个是vertex数组定长 31，n只是记录实际用了多少，扩课程得改数组长度和循环上界两处，不是一个纯粹的常量替换。

2.2 initGraph：初始化的顺序不能乱

初始化函数看着只有几行，但它要同时完成三件事：给外壳分配内存、给每个顶点分配内存、把编号和出边指针填成初值。顺序反了或者漏了边表指针清空，后面插入边的时候就会踩到野指针。

pGraphList initGraph(void) { int i; pGraphList pList; pList = (pGraphList)malloc(sizeof(struct graphList)); for (i = 0; i < 31; i++) pList->vertex[i] = (pVertexNode)malloc(sizeof(struct vertexNode)); pList->n = 31; for (i = 0; i < 31; i++) pList->vertex[i]->vertexInfo = i + 1; /* 编号从 1 开始 */ for (i = 0; i < 31; i++) pList->vertex[i]->next = NULL; /* 出边链表必须先清空 */ return pList; }

注意这里没有给inDegree赋初值——入度不是建图时能确定的，它取决于有多少条边指向这个顶点，必须等全部边插完之后统一扫一遍算出来。源程序把这一步单独抽成了findIndegree，好处是建图和算入度彻底解耦，坏处是如果有人忘了调用，inDegree就是malloc出来的随机值，拓扑排序的初始入队会变成玄学行为。我的习惯是在initGraph里顺手把inDegree也置 0，多一行代码，省掉一整类排查。

2.3 链式队列：为什么不用数组队列

BFS 版本的拓扑排序需要一个先进先出的容器，把「入度刚变成 0」的顶点先攒起来。理论上开一个int queue[31]加头尾指针完全够用，顶点最多进队一次，容量上限是确定的。源程序还是选了链式队列，用head和rear两个指针维护，理由是队列操作的接口更干净——enQueue/deQueue/getQueueHead三个函数把指针操作全封在内部，主流程里看不到数组下标。

void enQueue(pLinkQueue pQueue, int x) { pNode p; p = (pNode)malloc(sizeof(struct node)); if (p == NULL) { printf("Out of space!\n"); return; } p->info = x; p->link = NULL; if (pQueue->head == NULL) /* 空队列：头尾都指向新结点 */ pQueue->head = p; else pQueue->rear->link = p; /* 非空：挂到尾部 */ pQueue->rear = p; }

这段代码里有三处是链式队列入门的常见卡点。第一，入队前必须判断队列是否为空，空队列时rear还没有指向任何结点，直接rear->link = p会解引用空指针。第二，rear更新必须放在 if-else 外面，两条分支都执行，漏掉就会出现「第二个元素之后全丢」的现象。第三，出队的deQueue只释放了结点、没有把rear复位，队列被清空后再入队就会拿一个悬空的rear去挂钩，这是链表队列最经典的后悔药场景——第一次清空之后再跑就崩。

提示：定长数组版队列其实更适合这个场景，31 个顶点最多进队 31 次，用两个下标加取模就行，没有malloc、不会泄漏、也不会出现rear悬空。链式队列的价值在于演示「队列的链式实现」这个数据结构考点，如果只是想把课表排出来，数组版更省心。

3. 核心链路走读：从 initGraph 到 topoSort，一个入度为 0 的顶点怎么被推着走

整个程序的主干其实只有四步：建图、逐条插边、算入度、跑拓扑排序。main里那一大串initEdgeList调用看着吓人，但它就是一张手写的边表——每一行代表「某门课是另一门课的先修课」。真正需要读透的是插边、算入度、BFS 主循环这三个函数，它们串起来就是一个完整的 Kahn 算法。

3.1 initEdgeList：一条边是怎么挂上去的

函数签名initEdgeList(pList, x, index)的三个参数里，index是边的起点（顶点数组下标，从 0 开始），x是边的终点（课程编号，从 1 开始）。这两个参数的下标基准不一致，是这份代码里最容易看走眼的地方。

pGraphList initEdgeList(pGraphList pList, int x, int index) { pEdgeNode p1, p2; pVertexNode p3; p1 = (pEdgeNode)malloc(sizeof(struct edgeNode)); p3 = pList->vertex[index]; /* index 是数组下标，直接取 */ if (p1 == NULL) { printf("Out of space!\n"); return pList; } p1->index = x; /* x 是课程编号 1..31 */ p1->next = NULL; if (p3->next == NULL) p3->next = p1; /* 第一条出边 */ else { p2 = p3->next; while (p2->next != NULL) /* 尾插：先走到链表末尾 */ p2 = p2->next; p2->next = p1; } return pList; }

拿initEdgeList(pList, 15, 0)举例：index = 0对应课程 1「高等数学」，x = 15是课程编号 15「数值分析」，这条边的语义就是「高等数学 → 数值分析」。同理initEdgeList(pList, 9, 3)是「C 语言程序设计（4）→ 数据结构（9）」。整张图的边都靠这一串调用堆出来，源程序里的顺序是按起点分组的，读的时候按index归一下类会清楚很多。

这张表只列了五行，但已经把「一门基础课能扇出多少条边」说清楚了。C 语言一口气扇出六条边，说明它是整个课程体系的地基；而像 26 分布式数据库、29 图像处理这种只有入边、没有出边的顶点，就是学习路线的终点。

插边用的是尾插法，每次都要沿着出边链表走到底，单条边的时间是 O(出度)。31 个顶点、四十来条边的规模完全无所谓，但如果把课程数扩到几百门、边数上千，尾插会退化得比较明显。常见做法是改成头插——新边直接插在链表头，代码只有三行，反正拓扑排序遍历出边时并不关心顺序：

/* 头插版：O(1) 插边，遍历顺序与插入顺序相反，不影响拓扑结果 */ p1->next = pList->vertex[index]->next; pList->vertex[index]->next = p1;

3.2 findIndegree：扫描全部边表，把入度算出来

入度的定义很直白：有多少条边指向我，我就有几门先修课。所以算法就是遍历每个顶点的出边链表，每遇到一条指向v的边，就把v的入度加一。由于边上存的是课程编号（1..31）而不是数组下标（0..30），落数组时必须减一。

void findIndegree(pGraphList pList) { int i; pEdgeNode p; for (i = 0; i < pList->n; i++) pList->vertex[i]->inDegree = 0; /* 先清零，否则重复调用会累加 */ for (i = 0; i < pList->n; i++) { p = pList->vertex[i]->next; while (p != NULL) { pList->vertex[p->index - 1]->inDegree++; /* 编号 1..31 -> 下标 0..30 */ p = p->next; } } }

第一个循环的清零容易被当成废话跳过，但只要topoSort被调用两次（比如后面要按学期分段重排），不清零就会在上一轮的结果上继续累加，排序直接乱套。第二个循环里的p->index - 1是整个程序里最容易漏的减一，源程序作者自己也提到过「程序输出一直不符合要求，单步跟踪时才想起编号从 1 开始」——说的就是这类错位。

时间开销上，清零是 O(n)，扫边是 O(e)，合计 O(n+e)。这个复杂度在 31 个顶点的规模下基本感觉不到，但它在结构上很重要：后面主循环的复杂度也是 O(n+e)，两段加起来整体还是 O(n+e)，这就是为什么拓扑排序被认为是很「便宜」的算法。

3.3 topoSort：BFS 主循环与那个全局数组

Kahn 算法的思路用一句话概括：反复找出当前入度为 0 的顶点，输出它，然后把它所有后继的入度减一，减到 0 的继任者进入下一轮候选。队列在这里承担的角色是「本轮候选池」，保证同一批可以并行学习的课程被连续处理。

int pTopo[31]; /* 存放拓扑排序结果，全局 */ void topoSort(pGraphList pList) { int element, i, n = 0, k; pLinkQueue pQueue; pEdgeList p; findIndegree(pList); /* 先把入度算准 */ pQueue = creatEmptyQueue(); for (i = 0; i < pList->n; i++) if (pList->vertex[i]->inDegree == 0) enQueue(pQueue, pList->vertex[i]->vertexInfo); /* 第一批：无先修课 */ while (!isEmptyQueue(pQueue)) { element = getQueueHead(pQueue); deQueue(pQueue); pTopo[n++] = element; /* 出队即定稿，写进结果序列 */ p = pList->vertex[element - 1]->next; while (p) { /* 遍历它的所有后继 */ k = p->index; pList->vertex[k - 1]->inDegree--; if (pList->vertex[k - 1]->inDegree == 0) enQueue(pQueue, pList->vertex[k - 1]->vertexInfo); p = p->next; } } if (n < pList->n) /* 有顶点没进过队，说明有环 */ printf("The AOV network has a cycle!\n"); }

几个参数和细节值得单独说。n是已定稿的顶点计数，它既当写指针用，又当环检测的判据——如果图里存在环，环上所有顶点的入度永远减不到 0，它们永远不会进队，最后n < pList->n就成立了。这个检测只打印一句话，没有返回值也没有中断，主函数照样会拿一个残缺的pTopo去打印，所以真要用于生产，得让它返回一个状态码，让调用方决定是重排还是报错。

pTopo定成全局变量，源程序里给的理由是「放数组里返回主函数会丢数据」。这个现象在 C 里其实很好解释：函数内部定义的数组分配在栈上，把它的地址返回给调用方，函数一返回栈帧就失效了，那块内存随时会被下一次函数调用覆盖，能正确打印出前几个元素纯属运气。正确做法是由调用方传进来一块缓冲区，或者malloc一块堆内存由调用方负责释放。全局数组是最省事的绕法，代价是topoSort变成了不可重入的——想同时排两张图就不行了。

注意：pTopo[n++] = element存的是课程编号，主函数里打印时要写array[pTopo[i] - 1]，又是一次减一。整份代码里「编号 ↔ 下标」的转换出现了四五处，读懂它的最快方式是拿一张纸，把所有-1和+1的位置圈出来。

4. 广度优先还是深度优先：一次把课表排成「C 语言→数据结构→算法」的反面教材

拓扑排序和遍历方式是两个正交的维度：Kahn 算法天然对应 BFS，DFS 逆后序也能得到合法拓扑序。两者排出来的结果都满足「先修课在前」，但给人的可读性完全是两回事。这个问题在课程表场景下特别明显，因为课程依赖图是天然分层的——大一基础课、大二专业课、大三方向课，层与层之间有大量并行关系。

4.1 DFS 排出来是什么样：一路扎到底

把同样的邻接表交给 DFS，递归函数会从顶点 1 出发，顺着第一条出边一直往下钻，钻到没有出边为止才回溯。逆后序写结果的写法大致是这样：

static int visited[31]; static int dfsTop = 0; void dfsVisit(pGraphList pList, int v) { pEdgeNode p; visited[v] = 1; for (p = pList->vertex[v]->next; p != NULL; p = p->next) { if (!visited[p->index - 1]) dfsVisit(pList, p->index - 1); } pTopo[dfsTop++] = v + 1; /* 后序位置写入，最终序列需要整体反转 */ }

结果是合法的——反转之后每条边u → v都能保证u排在v前面。但它不保证「基础课扎堆出现在前面」。源程序里举的例子很典型：C 语言程序设计、数据结构、算法设计与分析这条链，DFS 会一路钻到底，把这三门课连着排出来，然后才回头处理同样是入度为 0 的高等数学、电路理论。最终序列读起来像这样：C 语言 → 数据结构 → 算法设计与分析 → 高等数学 → 电路理论 → 模拟电子技术。从约束角度挑不出毛病，从教务角度完全没法用——学生第一学期就要学算法，而高数被排到了后面。

这就是 DFS 在这个场景下的根本问题：它优化的是「深度」，而排课需要的是「宽度」。层与层之间的并行关系被压扁成了一条线，同一层的课程被迫分出了先后。

4.2 BFS 排出来为什么符合直觉：分层由入度自然决定

Kahn 算法的入队时机由「入度归零」决定，而入度归零只可能发生在「所有先修课都已经被排出去之后」。这带来一个很好的性质：队列里的顶点天然属于同一层或者相邻层，先出队的必然是更基础的课程。

拿源程序的图跑一遍前几轮：初始扫描时入度为 0 的是 1、2、3、4、5 五个顶点（分别是高等数学、概率论与数理统计、线性代数、C 语言程序设计、电路理论），它们全部入队，这就是「第一学期候选」。出队 1 号，把它的两个后继（15 数值分析、28 计算机图形学）的入度各减一，还没归零，不着急；出队 2、3 号，数值分析的入度继续往下掉，到 3 号处理完刚好归零，进队；出队 4 号，C 语言的六个后继里 8、9、10、24、28 这几门的入度同时归零，一股脑进队。整个过程就像水位线往上漫，每一层什么时候浮出来完全由依赖关系决定，不需要人为指定。

/* 出队顺序即分层顺序，可以顺手记录每个顶点落在第几层 */ int level[31] = {0}; /* 在 topoSort 的后继处理里加一行 */ if (pList->vertex[k - 1]->inDegree == 0) { level[k - 1] = level[element - 1] + 1; /* 后继比当前顶点深一层 */ enQueue(pQueue, pList->vertex[k - 1]->vertexInfo); }

这段小改动只有一行，但它把「一条排序结果」变成了「一张带层号的课表」。level[0]到level[30]里的最大值就是整张图的深度，也就是教学计划至少需要几个学期才能排完。后面第 6 章会基于它做学期划分。

4.3 两种遍历的取舍标准

不是所有 AOV 网都该用 BFS。判断依据其实看图的形状：如果这张图的层数深、每层顶点少，DFS 和 BFS 排出来的差别不大；如果图是「宽扁型」，底层有大量并行顶点，BFS 的分层效果就明显得多。课程计划、项目构建依赖、任务流水线这类图基本都是宽扁型，基础任务数量多、汇聚点靠后，BFS 天然合适。反过来，像表达式求值、语法树遍历这类需要「一路到底」的场景，DFS 才是正确选择。

另一个维度是结果稳定性。BFS 的结果取决于初始扫描顺序和出队顺序，同一个图只要顶点编号固定，跑多少次结果都一样，这对排课很重要——教务处可不想每次运行都得到一张不同的课表。DFS 的结果除了依赖顶点顺序，还依赖每条出边的遍历顺序，改一下插边的方式（头插换尾插）结果就会变。要复现、要对比、要写进论文里当实验数据，结果稳定的那个更省心。

5. 编译运行与排查：31 个顶点跑不通时先看这五处

这份源程序是标准的 C89 风格，除了malloc和printf没有别的外部依赖，随便找个编译器都能过。但它跨了 Turbo C 2.0 和 VC 两个年代，有些写法在新编译器上会报警告，有些行为在老编译器上正常、在新编译器上翻车，跑之前心里有个数。

5.1 三步跑起来

最省事的路子是用 gcc 直接编，一条命令搞定，不用建工程也不用配头文件路径。源码里没有用到任何平台相关的东西，stdio.h和stdlib.h就够。

# 1. 把源程序存成 lesson_plan.c gcc -std=c89 -Wall -o lesson_plan lesson_plan.c # 2. 运行，直接看终端输出 ./lesson_plan # 3. 想存成文件做对比，重定向一下 ./lesson_plan > topo_result.txt

-Wall打开后大概率会看到两类警告：一是malloc的返回值被赋给指针时没做显式转换（C 里本来就不需要，但老代码通常写成强制转换），二是main函数没有显式return 0。这两类都不影响运行，但建议看一眼有没有「可能未初始化」这类真问题。如果用的是 Windows 上的新版 MSVC，scanf相关的安全检查会报错，不过这份代码里没有scanf，基本无感。

跑通之后核对结果的方法很朴素：人工拿纸笔对这张图做一遍拓扑排序，看看关键课程的相对位置对不对。重点检查三条链——1→15→23（高数→数值分析→人工智能）、4→9→22（C 语言→数据结构→算法设计与分析）、4→8→21（C 语言→面向对象→软件工程）。只要这三条链的先后顺序对了，其余的基本不会错。

5.2 五条踩坑记录

现象一：输出序列里某门课出现了两次，或者干脆少了几门。原因多半是findIndegree被调用了两次而中间没有清零，入度在原有基础上累加，导致本该归零的顶点永远归不了零，最后被环检测那句has a cycle误报成有环。解决办法是把清零循环放在函数最前面（源程序就是这么写的），或者在initGraph里就把inDegree置 0，两道保险。

现象二：程序跑完什么也不打印，或者打印出一堆乱码。这是典型的「返回了局部数组地址」。如果把topoSort改成返回int*，函数体里int result[31]一结束就失效了，主函数拿到的指针指向已被复用的栈内存。源程序用全局pTopo绕过了这个坑，代价是不可重入。要正经修，改成void topoSort(pGraphList pList, int *out)，由调用方提供缓冲区。

现象三：编译通过、运行不崩，但排序结果明显违反先修关系。八成是p->index - 1漏了减一，或者pTopo[n++] = element之后主函数按array[pTopo[i]]取值。编号从 1 开始、下标从 0 开始，这两个基准在这份代码里混用了十几次，源程序作者自己也是单步跟踪时才偶然发现的。我的血泪经验是：凡是看到->index和vertex[，先问一句这里该不该减一。

现象四：换一台机器跑，前几个结果一样，后面全变了。如果代码里用了未初始化的指针或者数组越界写，行为就会依赖编译器把栈上哪块内存分配给你。典型触发点是initGraph里忘了清空next，插入边时拿到野指针，往随机地址写数据。用valgrind ./lesson_plan或者开-fsanitize=address编一遍，这类问题会当场现形。

现象五：想加几门课，改了课程表但程序还是排 31 个。课程数在代码里硬编码了至少四处：vertex[31]的数组长度、initGraph里三个for (i = 0; i < 31; i++)、pTopo[31]的长度、主函数里array[31]的长度和for (int i = 0; i < 31; i++)的循环上界。改课程数得把这几处全对上，漏一处就会出现少排或多排。稳妥做法是定义一个#define COURSE_NUM 31，全部替换成宏。

提示：环检测那行printf("The AOV network has a cycle!\n")只打印不返回，主函数会继续用一个不完整的pTopo去索引课程名数组，越界读的可能就是野内存。调试阶段建议在它后面直接exit(1)，先把问题暴露出来。

6. 二次开发：把一条拓扑序列改造成带学期分层和学分约束的课表

原始程序只输出一条线性序列，离真正能看的教学计划还差两步：分学期、控负载。这两步都能在拓扑排序的骨架上做增量改造，不用推翻重写。第一步是给每个顶点记层号，level[k-1] = level[element-1] + 1那一行就是全部的改动量，跑完一遍max(level)就是最少需要的学期数。第二步是在分层之后做学分装箱——每门课挂一个学分字段，从第 1 学期开始往里塞，塞不下就顺延到下一学期，但顺延不能违反先修约束，所以每门课的最早允许学期是max(先修课所在学期) + 1。

/* 按学期分层：credit 为每门课的学分，limit 为每学期学分上限 */ void planByTerm(pGraphList pList, int *credit, int limit) { int term[31] = {0}; /* 每门课安排在第几学期 */ int load[16] = {0}; /* 每学期的学分负载 */ int i, k, t, changed = 1; for (i = 0; i < pList->n; i++) if (pList->vertex[i]->inDegree == 0) term[i] = 1; /* 无先修课：第 1 学期 */ while (changed) { /* 反复扫描，直到不再有课被安排 */ changed = 0; for (i = 0; i < pList->n; i++) { if (term[i] == 0) continue; for (pEdgeNode p = pList->vertex[i]->next; p; p = p->next) { k = p->index - 1; int need = term[i] + 1; /* 后继最早下一学期 */ int t2 = need; while (load[t2] + credit[k] > limit) /* 该学期放不下就顺延 */ t2++; if (term[k] == 0 || t2 < term[k]) { term[k] = t2; load[t2] += credit[k]; changed = 1; } } } } for (t = 1; t <= 8; t++) printf("第 %d 学期负载 %d 学分\n", t, load[t]); }

这段代码里有两点值得说。一是while (load[t2] + credit[k] > limit) t2++;这行是负载均衡的核心，它把「学分超了」转换成「往后挪一个学期」，挪到能放下为止；没有上界保护，如果某门课学分比limit还大就会死循环，实际用的时候得加个最大学期数判断。二是if (term[k] == 0 || t2 < term[k])这个条件保证了同一门课被多条路径指向时取最早可行的学期，不会因为某条长链把课越推越晚。

验证改造是否正确的办法很简单：拿改造前后的结果做个比对，把所有边列出来逐条检查「起点学期 < 终点学期」，只要全部满足，分层就是合法的；再检查每学期的load[t]有没有超过limit，负载均衡也就验完了。这两条检查我一般会写成一个小脚本跑一遍，比肉眼扫三十行输出靠谱得多。

课程表本身也别硬编码在main里。现在那一大串initEdgeList(pList, 15, 0)换个专业就得全改，改成从文本文件读、每行「起点编号 终点编号」，代码一行不用动就能换一张图。孤立点（那些没有先修关系的公共必修课）在源程序里是排在最后手工穿插的，改造后可以直接在每学期负载没满的时候从孤立点池里补，保证学期学分均衡。

从那以后我每次做这种「依赖排序 + 资源分配」的活，都会先拿最小可跑版本验证一遍拓扑序，再往上叠约束——先分层、再装箱、最后做可视化，每加一层都回头验一次「先修关系有没有被破坏」。跳过这一步直接写完整排课逻辑，等结果不对的时候根本分不清是图建错了还是装箱写崩了。希望帮到你。

本文还有配套的精品资源，点击获取