简介：内容围绕教学计划编制中的课程先修关系与学习顺序展开，以AOV网和拓扑排序为核心，面向数据结构与图论课程设计、算法实践及需要安排课程体系的学习者。资料将课程依赖抽象为有向无环图，讨论广度优先与深度优先拓扑排序的差异，并结合高等数学、C语言程序设计、数据结构、算法设计与分析等课程，说明依赖建模、入度统计、邻接表表示及队列辅助BFS的实现过程，附有可运行的C语言源程序，便于对照论文理解从模型到代码的落地。压缩包共1个doc文件，约190KB，以论文文档形式呈现，适合作为课程设计报告或实验参考。已有297人学习，读者可据此掌握先修关系抽取、拓扑排序函数设计与排课结果验证思路，并借鉴其中的功能函数划分和邻接表组织方式。

1. 先修关系不是排序题：为什么 DFS 拓扑排序会把高数排到 C 语言后面

教学计划编制这件事，很多人第一反应是「给课程排个序」，抓一个拓扑排序模板套上去就完事。可一旦真拿深度优先去做，你会得到一个合法却荒唐的结果：C 语言程序设计、数据结构、算法设计与分析连着排完，高等数学才姗姗来迟。这个序列满足所有先修约束，却没有一所学校敢照它开课。问题不在代码写错，而在「合法序」和「可执行的教学计划」之间隔着一层语义：同一学期里可以并行的课程，必须被压到同一层，而不是被一条深度链拆散。把 31 门课建成 AOV 网只是起点，真正决定结果形状的，是你用队列还是用栈去驱动入度归零。

2. AOV 网建模：31 门课压进邻接表要付什么代价

2.1 顶点结构里的三个字段，决定了后面所有操作

整套程序的地基就三个结构体，先把它们看清楚，后面每一步操作才有落点。顶点里同时存了「课程编号」「入度」「出边链表头」；边结点只存「指向哪个顶点」和「下一条边」；整张图再包一层，记顶点总数和顶点指针数组。这种把「顶点属性」和「图容器」分开的设计，好处是顶点天然带状态，坏处是顶点必须动态分配，释放时得一个个来。

/* 邻接表的边结点：只关心"指向谁"和"下一条" */ struct edgeNode { int index; /* 目标顶点的编号，注意是 1-based */ pEdgeNode next; }; /* 顶点结点：课程信息 + 入度 + 出边表头 */ struct vertexNode { int vertexInfo; /* 课程代号，从 1 开始 */ int inDegree; /* 当前入度，拓扑排序的核心状态位 */ pEdgeList next; /* 指向第一条出边 */ }; /* 图的封装：顶点总数 + 顶点指针数组 */ struct graphList { int n; pVertexNode vertex[31]; };

inDegree放在顶点里而不是单独开一个数组，是个很实在的取舍：拓扑排序过程中要反复读写入度，放在顶点结构里能和vertexInfo一起被同一句pList->vertex[k-1]->inDegree--命中，缓存局部性好，代码也短。代价是这个字段成了「可变状态」，谁都能改，一旦某处忘了重置，整轮排序就废了——后面第 5 章会专门讲这类翻车。

vertex[31]用定长数组而不是二级指针，说明作者很清楚课程数是固定的 31 门。这省掉一次malloc的间接寻址，但也把「课程数可扩展」这条路堵死了，想加一门课就得改结构体定义。教学场景下这个约束可以接受，工程场景下就不行了。

2.2 为什么是邻接表而不是邻接矩阵

31 个顶点，实际有依赖关系的边只有三十来条，邻接矩阵要开 31×31=961 个格子，其中九百多个是空的。稀疏图的存储密度低到这种程度，选矩阵纯粹是跟自己过不去。

更关键的是操作模式。拓扑排序的核心动作只有两个：一是「找出所有入度为 0 的顶点」，二是「某个顶点出队后，遍历它的所有后继并把入度减一」。第二个动作直接对应「遍历一个顶点的出边集合」，邻接表是 O(deg)，邻接矩阵是 O(n)。31 个顶点时两者都无所谓，但如果课程表扩到几百门，矩阵每次都要扫一整行，白白浪费。

邻接表的代价也很明确：求入度反而变贵了。矩阵里入度就是第 j 列的非零个数，扫一列即可；邻接表里没有「入边表」，想知道谁指向你，必须把全图所有出边扫一遍。这就是为什么程序里必须有一个独立的findIndegree函数，而不能在建图时顺手算完——虽然后面会讲，其实建图时顺手++才是更划算的做法。

提示：稀疏图 + 频繁遍历出边，选邻接表；稠密图 + 频繁判断两点是否相邻，选邻接矩阵。这个判断标准在课程表、任务调度、编译依赖这几个场景里是通用的。

2.3 尾插法：一段看起来无害的 O(deg²)

initEdgeList每调用一次就往某条边表的尾部插一个结点。为了找到尾部，它从表头一路while(p2->next != NULL)走过去。单次插入是 O(deg)，对同一个顶点插入 deg 条边，总代价就是 O(deg²)。

pGraphList initEdgeList(pGraphList pList, int x, int index) { pEdgeNode p1, p2; pVertexNode p3; p1 = (pEdgeNode)malloc(sizeof(struct edgeNode)); p3 = pList->vertex[index]; /* index 是 0-based 的顶点下标 */ if (p1 == NULL) { printf("Out of space!\n"); } else { p1->index = x; /* x 是 1-based 的课程代号 */ p1->next = NULL; if (p3->next == NULL) { p3->next = p1; /* 空表直接挂头 */ } else { p2 = p3->next; while (p2->next != NULL) /* 走到尾，这是 O(deg) 的来源 */ p2 = p2->next; p2->next = p1; } } return pList; }

参数x是边的终点（课程代号，1-based），index是起点在数组里的下标（0-based）。这两个参数不同基准，是整份代码里最容易看错的地方，后面第 5 章的「整体错一位」就是从这儿埋下的。

尾插法唯一的好处是出边顺序和书写顺序一致，调试时看着舒服。想消掉这个 O(deg²)，两条路：一是头插，p1->next = p3->next; p3->next = p1;，两行搞定，代价是出边逆序；二是在vertexNode里再加一个tail指针，维护尾指针，插入 O(1)。31 门课的数据量下 O(deg²) 完全不痛，但从「这段代码会被拿去当模板」的角度看，头插法更值得推荐。

2.4 顶点编号从 1 开始：埋在数据结构里的索引债

initGraph里pList->vertex[i]->vertexInfo = i + 1，顶点数组下标是 0..30，课程代号是 1..31。之后每一次「拿代号找顶点」都要写vertex[代号 - 1]，每一次「拿下标找代号」都要+1。

pGraphList initGraph(void) { int i; pGraphList 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-based 代号 */ for (i = 0; i < 31; i++) pList->vertex[i]->next = NULL; /* 注意：inDegree 这里没有初始化 */ return pList; }

这段初始化有两个值得盯住的地方。第一，inDegree压根没赋值，malloc出来的是脏内存。程序能跑对，是因为findIndegree开头会先清零兜底；但只要有谁跳过findIndegree直接读入度，读到的就是随机值。第二，三次malloc全没判空，内存吃紧时会在后面某个地方莫名其妙地崩，而不是在这里干净地报错。

至于 1-based 编号，教学上确实贴近「第 1 门课」的直觉，但在 C 语言里，它把「代号」和「下标」永久性地分成了两套坐标。整个程序里-1和+1出现了十几次，只要漏一处，整张课程名表就整体错位。这类 bug 不报错、不崩溃，只是结果不对——最难查的那一类。

3. 入度才是驱动引擎：findIndegree 与队列推进的完整链路

3.1 入度不是声明出来的，是扫边扫出来的

因为邻接表只有出边，入度必须靠「把所有边过一遍，每见到一条 u→v 的边就给 v 的入度加一」得到。函数先把所有顶点的入度清零，再双重循环扫全图，总代价 O(n+e)。

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 */ p = p->next; } } }

这段代码的正确性依赖一个隐含前提：每条边只被存了一次。如果建图时不小心把同一条边插了两遍，入度会算成 2，后面减度时也减两次，结果仍然自洽——所以重复插边不会立刻暴露，只会让「入度归零」的时刻推迟，得不偿失。

更值得说的是：这个函数其实可以不存在。如果改成在initEdgeList里插边的同时pList->vertex[x-1]->inDegree++，一次建图就把入度算完了，省掉一整轮 O(n+e) 的全图扫描。作者选择分离，是为了让「建图」和「算入度」在代码上互不干扰，出问题时能单独定位是哪一步错。这是可维护性换性能，31 门课的数据量下完全值得。

注意：如果同一个图要做多次拓扑排序（比如反复试不同的学期划分方案），每次都必须重新调用findIndegree，因为上一轮已经把入度减到零了。忘了重置，第二轮会一个顶点都入不了队。

3.2 Kahn 主循环：一次出队、一次减度、一次判零

先把所有入度为 0 的顶点入队，然后循环：取队头、出队、记入结果、遍历它的所有后继、把后继入度减一、减到 0 就入队。整段逻辑非常短，短到容易被低估。

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"); }

pTopo[n++] = element这一行是整个算法的语义核心：一个顶点只有在它所有前驱都已经出队之后，入度才会归零，此刻它才第一次被写进结果数组。换言之，写入顺序天然满足「所有前驱都在它前面」，不需要任何额外校验。

代价是这段代码没有记录「层」。队列里同一时刻可能混着不同层次的顶点，程序一律 FIFO，出队顺序只保证拓扑合法，不保证同层聚集。这一点在第 4 章会展开。

3.3 环检测：n 与顶点总数的差额在说什么

如果图里有环，环上每个顶点都至少有一条来自环内的入边，它们的入度永远减不到 0，永远不会入队。于是while结束后，n（已输出的顶点数）小于pList->n。

这个判断很便宜，只要一次整数比较。但它只回答「有没有环」，不回答「环在哪」。想定位具体是哪几门课互为先修，得换算法：DFS 三色标记能找出回边，Tarjan 能一次找出所有强连通分量，后者才是「把环上的课全部列出来」的正解。

这里还有个隐藏的严重问题：检测到环之后只printf了一句，没有 return，也没有终止主流程。主函数照样按 31 次循环输出array[pTopo[i]-1]，而pTopo后面的位置根本没被写入，里面是 0，array[-1]直接越界读。这段代码在正常数据下跑得挺好，一旦有人改了课程依赖关系造出环，就会以段错误或者乱码课程名的形式收场。第 5 章会把它作为独立一条踩坑记录展开。

3.4 队列换成栈会怎样：一个字符的改动，语义全变

把enQueue换成push、deQueue换成pop，得到的结果仍然是合法的拓扑序——因为入队条件依然是「入度归零」，这个不变量没变。区别只在顺序倾向：栈是后进先出，刚解锁的后继会被优先处理，于是结果更像「一条链走到底」，同层课程被打散的概率大增。

真正会出错的是另一种写法：直接用 DFS 的前序输出。DFS 沿着第一条出边一路深入，访问到就打印，这样打印出来的顺序不保证是拓扑序。原文举的那个例子——C 语言、数据结构、算法设计与分析、高等数学、电子电路、模拟电子电路——正是这种前序输出的典型形态：先把 C 语言这条支链走完，才回头处理并列的高等数学。

要把 DFS 用对，必须用后序：等一个顶点的所有后继都访问完了，再把它加进结果，最后把整个结果逆序。这个逆序才是合法拓扑序，这是图论里的标准结论。所以「DFS 不能做拓扑排序」这个说法不准确，准确的说法是「DFS 前序不能，DFS 后序逆序能，但两者都不天然分层」。

3.5 分层：Kahn 算法其实自带「波次」

虽然现在的代码没记录，但 Kahn 算法的循环结构天然是分层的：while每转一轮，队列里那批顶点就是同一「波次」——它们的入度在同一时刻归零，意味着它们的所有前驱都已经在前面的波次里出完了。

想要把波次显式化，只需要在每轮循环开始时把队列当前长度存下来，然后只处理这么多元素：

/* 按层输出：每一轮处理的是同一波入度归零的顶点 */ int level = 0; while (!isEmptyQueue(pQueue)) { int layerSize = queueLength(pQueue); /* 本轮要处理的顶点数 */ level++; for (int t = 0; t < layerSize; t++) { int element = getQueueHead(pQueue); deQueue(pQueue); layer[level][layerCount[level]++] = element; /* 归入第 level 层 */ /* 后面的减度、判零入队逻辑不变，新入队的顶点属于下一层 */ } }

关键在于layerSize是在内层循环之前取的快照。如果放在for条件里写成t < queueLength(pQueue)，队列长度会在循环中变化，新入队的下一层顶点会被当成本层处理，分层直接失效。这是分层拓扑排序最经典的一个实现陷阱。

分层之后，「层号」就对应「至少需要几个学期」这个下界：所有先修链最长的那条有多深，就至少要排多少个学期。31 门课的实际层高通常在 6 到 8 层之间，和本科前几年的学期数差不多，这不是巧合。

4. 从拓扑序到教学计划：把「波次」翻译成学期

4.1 一层一学期？先看层高和课程量

层号给出了学期数的下界，但直接「一层一学期」往往会翻车。原因是各层课程量极不均匀：基础层可能只有高等数学、线性代数、C 语言三四门，中间某一层却同时堆了数据结构、计算机组成原理、汇编语言、面向对象编程技术七八门，再加一门数值分析。一门课按每周 4 学时算，七八门就是三十多学时，学生没有喘息空间。

合理的做法是允许「相邻层合并」和「单层拆分」。合并的前提是层与层之间没有直接依赖被破坏——把第 k 层和第 k+1 层放进同一学期是可以的，因为第 k+1 层的顶点只依赖第 k 层及更早的顶点，同学期内先后修读在制度上说得通（很多学校确实允许同学期先修课与后继课并存，只要考试安排错开）。拆分则更微妙：同一层的课彼此无依赖，理论上可以拆到两个学期，但要注意拆分后不能造成「后继课比它的先修课还早」的荒唐安排。

4.2 孤立点与公共课：入度为 0 的「假基础课」

原文提了一句很实在的话：马列、哲学这类公共课和其他课程没有关联，在 AOV 网里是孤立点——入度和出度都是 0。它们在拓扑排序第一轮就全部入队，和高等数学、C 语言一起挤进第一学期，把第一学期的课表撑爆。

正确的处理是先分类再排：建图时标记出「入度 0 且出度 0」的顶点，单独放进一个池子，等专业课的学期骨架搭好之后，再按每学期的学分余量均匀撒进去。这个动作看着像「补丁」，其实背后有个原则：拓扑排序解决的是约束满足，不是资源分配。孤立点没有任何约束，它们的位置只受学分上限这个资源条件支配，属于另一个问题。

/* 筛选孤立点：入度和出度同时为 0 的顶点不参与学期骨架 */ int isIsolated(pGraphList pList, int idx) { if (pList->vertex[idx]->inDegree != 0) return 0; if (pList->vertex[idx]->next != NULL) return 0; /* 有出边，不是孤立点 */ return 1; }

注意这里用的是inDegree，而findIndegree必须在调用它之前跑过。如果顺序反了，读到的是malloc的脏值，孤立点判断会随机漏掉几门课——又是一个不报错只出错的地方。

4.3 学分与课时：拓扑序只是约束，不是目标函数

拓扑序保证「先修在前」，但它对「每学期多少门」完全无感。想要均衡，就得在分层的基础上再叠一层装箱逻辑：给每学期设一个学分上限，按层顺序往下走，能塞就塞，塞不下就开新学期。

/* 按层装箱：cap 是每学期学分上限，credit[i] 是第 i 门课的学分 */ int term = 0, used = 0; for (int lv = 1; lv <= maxLevel; lv++) { for (int i = 0; i < layerCount[lv]; i++) { int c = layer[lv][i]; if (used + credit[c] > cap) { /* 装不下，开新学期 */ term++; used = 0; } assign[c] = term; used += credit[c]; } }

这是贪心，不保证最优。真正的均衡排课更像带先修约束的多处理器调度问题，是 NP 难的，教学场景里没人会去求精确解。贪心的价值在于：规则简单、结果可解释、调整方便——教务处真去改的时候，能说清「为什么这门课排在这一学期」。

4.4 拓扑序不唯一：这份「自由度」怎么用

同一张 AOV 网，拓扑序可能有几十上百种。这个「不唯一」不是缺陷，是优化空间。入度同时归零的几门课，谁先谁后都不违反约束，那就可以按别的标准排：学分高的先排（早点腾出后面的负载）、学期负载轻的优先（削峰）、实验课和理论课交替（避免一周全是实验）。

队列只提供 FIFO，想按权重出队就得换优先队列。把enQueue改成按学分或按「剩余学时」维护的堆，Kahn 算法的主体一行不用改，出队顺序就带上了业务含义。这是拓扑排序最常见的工程改造方式：约束用图保，偏好用队列保，两者互不干扰，出问题时能分开定位。

5. 常见问题排查：只输出前几条、课程名错位、入度不归零

5.1 现象：结果只剩前面几条，后面全丢

原文记录得很清楚：把pTopo定义在topoSort里当局部数组、再返回给主函数用时，turboC 2.0 能显示前 29 条，VC 只能显示前 2 条。同一份代码换编译器结果不同，看起来像玄学，其实是典型的返回栈上数组。

原因很硬：局部数组分配在函数栈帧上，topoSort一返回，栈帧就被回收。主函数拿到的指针仍然指向那块内存，但内容随时可能被后续函数调用（包括printf自己的栈操作）覆盖。turboC 的栈布局宽松，前 29 个元素侥幸没被踩；VC 的调用约定不同，很快就覆盖了。这不是「turboC 更对」，只是「还没踩到」。

解决办法有三条，按推荐度排：调用方把数组传进来（void topoSort(pGraphList pList, int result[])），或者把结果放进堆（malloc后由调用方free），或者用原文的全局变量。全局变量最省事，但把「函数返回值」这件事变成了隐式契约，一旦有第二处调用，结果就互相覆盖。原文选了全局，并老老实实写了注释解释，这是诚实但不够好的选择。

5.2 现象：课程名整体错一位，或者某几门课名字张冠李戴

原因几乎总是 1-based 代号和 0-based 下标混用。程序里pList->vertex[element-1]、pList->vertex[p->index-1]、array[pTopo[i]-1]三处都在做减一，任何一处漏掉，或者反过来多减一次，结果就整体偏移。

这类 bug 的特点是不崩溃、不报错、只是不对。原文作者的解法是单步跟踪，一路盯着element和vertex下标的实际值，才在一个偶然的瞬间意识到「课程代号是从 1 开始的」。这个描述很真实——索引债就是这样，读代码时看不出问题，跑起来才露馅，而露馅的方式是「结果像是对的，只是错位」。

根治的办法是在入口处统一：要么全部 0-based，输出时再+1转成给学生看的编号；要么干脆把课程名和代号做成一张表，输出时查表，彻底切断「代号即下标」的心智负担。

5.3 现象：程序不报错，但少输出了几门课，也没有环的提示

这条是原文里潜得最深的坑。topoSort末尾的环检测只打印一句话，没有中断流程：

if (n < pList->n) { printf("The AOV network has a cycle!\n"); /* 这里应该 return，但没有 */ }

主函数仍然按for (i = 0; i < 31; i++)输出pTopo[i]，而pTopo从第n位开始全是 0，array[-1]直接越界读取，读到什么全凭运气——可能是乱码课程名，可能是段错误，也可能看起来「正常」地少了几行。现象是「少输出了几门课」，根因在环检测没有成为真正的守卫。

正确的写法是在检测到环时立刻返回，并让调用方知道排序失败：改成返回int（0 表示有环，1 表示成功），主函数拿到失败就停止输出。这比打印一句话后继续跑要安全得多。

5.4 现象：队列相关操作偶发崩溃，或者rear指向已释放内存

deQueue出队最后一个元素时，pQueue->head = p->link会把head置为NULL，free(p)释放结点，但rear仍然指着那块已被释放的内存，成了悬垂指针。isEmptyQueue用的是head == NULL，所以判空不会错；可一旦有人改动判空逻辑写成rear == NULL，或者后续enQueue依赖rear->link，就会踩到已释放的内存。

void deQueue(pLinkQueue pQueue) { pNode p; if (pQueue->head == NULL) { printf("Empty queue.\n"); } else { p = pQueue->head; pQueue->head = p->link; free(p); /* 缺少：if (pQueue->head == NULL) pQueue->rear = NULL; */ } }

修复只有一行：出队后如果head变成NULL，同步把rear也置为NULL。链式队列里「尾指针悬垂」是这个数据结构最经典的坑，判空逻辑写得再对，只要后面有谁碰rear，就得还这笔债。

5.5 现象：内存检查工具报警，或者长时间运行后内存持续增长

initGraph里 31 次malloc分配顶点，initEdgeList里每条边一次malloc，全程序没有任何一处free。deQueue释放的只是队列结点，图本身从头到尾没被回收。单次运行、进程退出，操作系统会兜底，看起来没事；但如果这份代码被嵌进一个反复调用的服务里，每调用一次漏一次图，内存曲线就是一条稳定的上升直线。

补齐释放逻辑要注意顺序：先释放每个顶点的出边链表（遍历vertex[i]->next逐个free），再释放顶点本身，最后释放graphList。反过来先释放顶点，出边链表的头指针就丢了，后面必然内存泄漏。

6. 设计取舍：拓扑序的「正确」与教学计划的「合理」之间隔着什么

把整件事收拢一下，会看到一条很清晰的界线：拓扑排序保证的是可行性，教学计划要求的是合理性，两者之间隔着分层和装箱两道加工。原文的程序把第一道加工做到了一半（用队列而非栈，方向对了），第二道完全没做（层号没记，学分没管），所以它输出的是一个「合法的课程序列」，还不是「能拿去排课的学期表」。

三种驱动结构的差别值得用一张表钉住：

这张表能解释很多「为什么我的拓扑排序结果看着怪」的问题：合法性只跟「入度归零才出队」这个不变量有关，跟用队列还是栈无关；而结果的「形状」跟驱动结构强相关。想要学期感，就必须显式记录层次，光换个队列是不够的。

验证这一步，我一般会做三道检查。第一道，输出数组长度必须等于顶点数，少于就说明有环或者有顶点没入队；第二道，对每条边 u→v，检查 u 在结果数组里的位置是否严格小于 v，这是 O(e) 的全量校验，比人眼靠谱；第三道，把层号打出来，看看层高和学期数差多少，差得离谱就说明某几层的依赖关系画错了。三道都过，再去看每学期的学分分布。

至于内存和索引那两笔债，我的习惯是写完图结构就先写destroyGraph，哪怕暂时用不上——写完释放逻辑，等于逼自己把每块malloc的归属想清楚一遍。索引基准则在文件头写一行注释钉死：「本文件内所有顶点访问一律 0-based，输出时 +1」，后面所有-1都有据可依，不会再出现那种「单步跟踪到偶然想起」的翻车。

从那以后我每次写带状态的图算法，都强制走一遍「先写释放、再写索引约定、最后才写主逻辑」的顺序。听上去是给自己加活，实际省下的是排查悬垂指针和整体错位的时间——这两类 bug 不报错，只让你怀疑人生。希望帮到你。

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