简介：面向计算机专业学生与数据结构、图论算法学习者，这份文档围绕教学计划编制这一典型的 AOV 网应用展开。内容以论文形式梳理问题建模思路：把课程视为顶点、先修关系视为有向边，通过统计入度并使用广度优先拓扑排序，排出符合实际教学规律的学习顺序；同时对比深度优先游走可能造成的课程割裂问题，说明为何选用 BFS 更贴合并行开课的现实需求。资源为单个 doc 文档，约 190KB，内含完整的课程 AOV 网分析、邻接表结构设计、31 门计算机系课程的先后关系表，以及可直接运行的 C 语言源程序。函数层覆盖图初始化、空队列创建、判空、入队出队、取队头、入度统计与拓扑排序等模块，便于读者对照代码理解算法实现细节。已有 297 人学习下载，适合作为数据结构课程设计、算法作业或图论应用练习的参考范例。

1. 教学计划编制：31 门课怎么变成一张能运行的先修关系图

排课表看着像教务处的日常事务，真落到课程设计里，它是一道标准的图论题。教学计划编制问题的关键不在于“哪门课更重要”，而在于“哪门课必须先于哪门课”。高等数学没学，数值分析开了也听不进去；C 语言没动手写过，数据结构基本就是天书。培养方案里 31 门专业课被一张先修关系网牢牢连在一起，手工排一次要改十几遍，改完还容易漏掉某条链条。这份教学计划编制问题的论文与源程序，做的事情很具体：把 31 门课建成 AOV 网，用广度优先的拓扑排序一次性排出满足全部先修约束的学习序列，再按学期课时量把通识类公共课插回去。它适合正在做数据结构课程设计、需要交一份能跑出正确序列的完整方案的人，也适合想拿一个真实图算法案例来练手的开发者。

2. 课程关系建模：把 31 门课压成一张 AOV 网的三个步骤

建模这部分决定了后面所有代码的天花板。图建错了，拓扑排序写得再漂亮，输出的也是一张废课表。我见过的翻车案例里，八成问题都出在这一步：要么边的方向反了，要么把不该进图的课程塞了进去。

2.1 顶点与边的定义：先修关系为什么天然是有向无环图

先把顶点定下来：31 门有先修关联的专业课，一门课一个顶点，编号 1 到 31。高等数学是 1，C 语言程序设计是 4，数据结构是 9，算法设计与分析是 22，一路编到多媒体技术 31。这些编号不是随手排的，它要和后面数组下标、课程名数组一一对得上，所以录入阶段就要固定下来，别中途改。

边就更有讲究了。边 A→B 的含义只有一个：A 是 B 的直接先修课，A 必须排在 B 前面。方向绝不能反过来，因为拓扑排序拆的是入边，入度减到 0 才允许出队。如果把边录成 B→A，程序照样能跑完，输出照样是 31 个课程，但顺序全错，而且不会报任何错，属于最难查的一类问题。

举一段真实数据。高等数学的出边有两条：指向数值分析 15，指向计算机图形学 28。意思是高数不过关，这两门课都别想开。C 语言程序设计的出边最多，指向数据结构 9、汇编语言 10、计算机组成原理 11、Matlab 编程技术 24、计算机图形学 28、嵌入式系统 30，六门课全都压在它后面。这种“一个基础课撑起半个培养方案”的结构，在图上一眼就能看出来，比翻培养方案的文字描述直观得多。

为什么这张图一定无环？因为先修关系本身有传递性，如果出现 A→B→C→A 这样的回路，就等于说学 A 之前要学完 A，培养方案在逻辑上就崩了，没有任何一种排课方式能满足它。所以合法的培养方案天然对应有向无环图，AOV 网正好是这个场景的标准建模工具。反过来说，程序里保留环检测不是多余动作，它是用来兜底的：万一边表录入时手抖多录了一条反向边，环检测能立刻把问题暴露出来，而不是让你对着一个缺了几门课的结果干瞪眼。

顶点上要挂两个信息：课程编号和入度。入度就是这门课有多少门直接先修课，是拓扑排序唯一的判断依据。出边表则记录它解锁了哪些后续课程。这两个字段一进一出，构成了整个算法的数据基础。

2.2 深度优先还是广度优先：一次排错的教学计划暴露的选型问题

拓扑排序的实现路径不止一条，深度优先和广度优先都能得到一个合法拓扑序，但“合法”和“符合教学规律”是两回事。

假设按深度优先的思路去遍历：从 C 语言程序设计出发，一路往下钻，先访问数据结构，再钻到算法设计与分析，这条链走到底才回头处理高等数学，接着是电路理论、模拟电子技术。最后排出来的序列可能是：C 语言程序设计、数据结构、算法设计与分析、高等数学、电子电路、模拟电子电路。

这个序列在数学上完全合法，每一条边都满足起点在前。但拿给教务看，第一学期只开 C 语言不开高数，第三学期才补数学基础，这明显不符合实际教学安排。深搜的问题是它认准一条链就往死里走，把本来可以并行推进的课程硬生生拉成了串行。

广度优先的做法不一样。它先把所有入度为 0 的顶点一次性入队——在这张图里就是高等数学、概率论与数理统计、线性代数、C 语言程序设计这几门没有任何先修要求的课。它们构成第一层，可以同期开课。然后逐个出队，把它指向的后继顶点入度减一，减到 0 的进下一批。这样天然形成“先铺基础、再推后继”的推进节奏，同一层次的课程会集中出现在序列的相邻位置。

这也是这套方案选队列而不是选递归的根本原因。队列是先进先出，先入队的先定稿，入度归零的先后顺序被严格保留；递归栈是后进先出，天然带着“钻到底”的倾向。选数据结构这件事，本质上是在选排课的教育逻辑，不只是选代码写法。

提示：如果导师追问“BFS 一定比 DFS 好吗”，标准答法是：两者得到的拓扑序都合法，但 BFS 的出队顺序与“入度归零时间”正相关，更贴近按学期推进的排课语义；DFS 更适合判断环和求逆拓扑序，不适合直接当课表用。

2.3 层次划分：从线性拓扑序到学期分配的映射

拓扑序是一维的 31 个编号，学期分配是二维的表格，中间需要一个映射。最简单的一步是用层号做桥梁。

在 BFS 主循环里顺便维护一个 level 数组：起点的层号为 0，当顶点 u 出队并把后继 v 的入度减到 0 时，令 level[v] = level[u] + 1。这样每个顶点都拿到了“最早可以在第几层开课”的信息，整个图的最大层号就是培养方案理论上的最短学期数下界——也就是关键路径长度。这一步不难，但它把“排出一个序列”升级成了“排出一张有学期概念的课表”，答辩时的分量完全不同。

层号只给出下界，不等于最终学期。真实排课还要看每学期的课时上限：一门专业课通常按周学时 4 到 6 计，一个学期排 5 到 6 门就到顶了。所以拿到层号之后，还要做一次“装箱”：同一层号内的课程按学分或周学时排序，超出上限的往下一个学期顺延，但顺延时必须保证它的所有先修课都在更早的学期里，这一步用层号已经能保证，不会冲突。

通识类公共课是另一类特殊情况。它们和其他课程没有任何先修关联，在图里就是入度为 0、出度也为 0 的孤立点。如果直接扔进图里跑拓扑排序，它们会全部堆在序列最前面，把第一学期撑爆。通常的做法是：建图时只放 31 门有依赖关系的专业课，公共课单独维护一张清单，等专业课排完、学期框架定好之后，再按每学期的剩余课时量填进去。这样既不破坏图的完整性，也符合实际教学里“公共课见缝插针”的安排方式。

做到这一步，模型层的工作就结束了：一张 31 个顶点的 AOV 网、一份层号数组、一张公共课待插清单。接下来才是代码要解决的事。

3. 数据结构选型：邻接表加链式队列的骨架怎么搭

模型定完，接下来是选容器。这一步看着琐碎，但直接影响复杂度怎么写、答辩怎么答，也影响后面调试时能不能一眼看出入度对不对。

3.1 为什么不用邻接矩阵：31 个顶点与稀疏边的取舍

31 个顶点，边表里实际录进去的边大约 30 条，平均每个顶点出度不到 1。这是一个非常稀疏的图。

用邻接矩阵的话，需要开 31×31 共 961 个单元，其中真正为 1 的只有 30 个，剩下 931 个全是 0。空间上不算灾难，31×31 的 int 数组才 4KB 左右，跑得动。但问题在遍历：拓扑排序里每次出队都要扫描该顶点的所有后继，矩阵做法得循环 31 次才能找出一条边，整体复杂度退化成 O(n²)。而邻接表只遍历真实存在的边结点，复杂度是 O(n+e)，在这张图上差了将近一个数量级。

更实际的一点是，课程设计的答辩几乎必问复杂度。你写 O(n²)，导师会顺势问“图这么稀疏为什么不用邻接表”；你写 O(n+e)，这个问题就自动消失了。选邻接表不只是为了跑得快，是为了让方案在逻辑上站得住。

3.2 顶点结点与边结点的内存布局

结构体分两层：顶点结点存课程编号、入度和出边表头指针；边结点只存后继课程编号和下一个边结点的指针。图本身用一个结构体封装，里面放顶点数 n 和一个顶点指针数组。

/* 边表结点：一条出边 */ struct edgeNode { int index; /* 后继课程的编号，取值 1~31 */ struct edgeNode *next; /* 同一下一个后继，尾插形成链表 */ }; typedef struct edgeNode *pEdgeNode; typedef struct edgeNode *pEdgeList; /* 顶点结点：一门课 */ struct vertexNode { int vertexInfo; /* 课程编号，从 1 开始，与课程名数组对应 */ int inDegree; /* 直接先修课门数，由 findIndegree 反算 */ pEdgeList next; /* 出边表头指针，NULL 表示没有后续课程 */ }; typedef struct vertexNode *pVertexNode; /* AOV 网封装：顶点数 + 31 个顶点指针 */ struct graphList { int n; pVertexNode vertex[31]; }; typedef struct graphList *pGraphList;

这里有个细节值得说：顶点数组存的是指针，每个顶点结点单独 malloc 出来。原始实现就是这么写的，跑得通，但严格说是 31 次独立分配。我一般会改成struct vertexNode vertex[31]直接内嵌，一次 malloc 搞定整个图，少 31 次分配，也少 31 个潜在的内存泄漏点。课程设计规模小，两种写法结果一样，但改成内嵌之后，initGraph里那个循环也省了，代码短一截，答辩时被问“有没有优化空间”正好拿来说。

边结点用尾插而不是头插，是为了让同一个顶点的出边顺序与录入顺序一致。调试时打印边表，看到的顺序和你照着培养方案录的顺序一样，比对起来快得多。头插虽然 O(1) 更快，但顺序全反，排查问题时反而添乱。

3.3 链式队列的四个基本操作与入度域的位置

队列用链式实现，两个指针：head 指向队首，rear 指向队尾。入队在 rear 后面挂结点，出队摘 head 并 free。判空就是看 head 是否为 NULL。取队首只读 info，不动指针。

/* 创建空队列，head 与 rear 同时置空 */ pLinkQueue creatEmptyQueue(void) { pLinkQueue pQueue = (pLinkQueue)malloc(sizeof(struct linkQueue)); if (pQueue != NULL) { pQueue->head = NULL; pQueue->rear = NULL; } else { printf("Out of space!\n"); } return pQueue; } /* 入队：队尾追加，注意空队列时 head 也要指向新结点 */ void enQueue(pLinkQueue pQueue, int x) { pNode 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 永远指向最后一个结点 */ }

入队这段代码里最容易漏的是空队列分支。少了pQueue->head = p这一行，第一个元素进队后 head 还是 NULL，后面判空直接返回 1，主循环一次都不进，输出空序列——而且编译不报错，运行不崩溃，属于典型的静默失败。

队列和图的耦合点只有一个：队列里存的是课程编号（1 到 31），不是顶点指针。这样做的好处是出队后可以直接用vertex[element - 1]定位顶点，代价是每次都要减 1，这也正是后面避坑章要重点讲的下标陷阱来源。

4. 拓扑排序落地：入度统计与 BFS 主循环的可复现代码

骨架搭好，核心算法其实只有两段：先把每个顶点的入度算出来，再用队列驱动主循环。两段代码加起来不到 40 行，但每一行都不能想当然。

4.1 入度统计：遍历边表反算 inDegree

建图阶段只录了边，没人告诉程序入度是多少。入度必须反算：遍历所有顶点，看谁的出边指向了谁，被指的那个顶点入度加一。

/* 反算入度：扫一遍全部边结点，被指向的顶点入度加一 */ 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; /* 顶点 i 的第一条出边 */ while (p != NULL) { pList->vertex[p->index - 1]->inDegree++; /* 编号从 1 起，下标要减 1 */ p = p->next; } } }

清零这一步不能省。拓扑排序里没有别的地方会重置入度，如果这个函数被调用第二次（比如测试时想重跑一遍），不清零的话入度会在旧值上继续累加，后面判断“入度是否为 0”就全部失效，输出一个空序列或者干脆卡死。

p->index - 1这个减一是第二个关键点。课程编号从 1 开始，数组下标从 0 开始，凡是“拿编号当下标”的地方都必须减一。这行代码写对了，后面主循环还得再写对一遍，漏一处就全乱。

跑完之后可以手工核一遍入度，这是最快的自检方式。这张图上，顶点 1（高等数学）入度 0，顶点 15（数值分析）入度 3，来自课程 1、2、3；顶点 28（计算机图形学）入度 3，同样来自 1、2、3；顶点 8（数据结构）入度 1，来自课程 4；顶点 30（嵌入式系统）入度 2，来自课程 4 和 12；顶点 23（人工智能）入度 2，来自课程 16 和 22。如果程序打印出来的入度表和手算对不上，别急着调排序，先回去查边表。

4.2 主循环：队列驱动的拓扑排序与环检测

主循环的逻辑很直白：所有入度为 0 的顶点先入队；然后不断出队，出队即定稿写进结果数组，同时把它指向的每个后继入度减一，减到 0 就入队；队列空了就结束。

/* 广度优先拓扑排序，结果写入全局数组 pTopo */ void topoSort(pGraphList pList) { int element, i, k, n = 0; pLinkQueue pQueue; pEdgeNode 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 != NULL) { 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放在出队之后、处理后继之前，保证一门课一旦出队就不再被修改，序列是单调向前推进的，不会出现后面的操作把已定稿的位置覆盖掉的情况。第二，环检测放在最后用n < pList->n判断，而不是在循环里加额外状态。原理是：有环的那部分顶点入度永远减不到 0，永远进不了队列，所以定稿数量一定小于顶点总数。这个判断几乎零成本，但没有它，程序遇到脏数据时会静默输出一个残缺课表，比直接报错难查得多。

4.3 结果输出与课程名校验：从编号序列到可读课表

算法出来的是 31 个编号，得翻译成课程名才有人看得懂。做法是建一个字符串数组，下标 0 对应课程 1，下标 30 对应课程 31，输出时用array[pTopo[i] - 1]取值。

/* 只列关键片段：编号与课程名的映射关系必须严格对齐 */ array[0] = "1.高等数学"; array[3] = "4.C 语言程序设计"; array[8] = "9.数据结构"; array[14] = "15.数值分析"; array[21] = "22.算法设计与分析"; array[30] = "31.多媒体技术"; topoSort(pList); for (int i = 0; i < 31; i++) printf("%s\n", array[pTopo[i] - 1]);

这个映射表看着简单，却是最容易出事的地方。课程名数组少写一项、或者顺序和编号错开一位，输出就会整体偏移，看着像排序错了，实际是翻译错了。所以跑完之后的第一件事不是看顺序对不对，而是先数一遍输出行数是不是正好 31 行、每门课是不是只出现一次。这两个检查都过了，再去核对先后关系。

边表录入部分的写法也顺带说一下。录入函数接收两个参数：后继课程编号 x，以及当前顶点在数组里的下标 index。调用initEdgeList(pList, 15, 0)的意思是“在顶点 0（即课程 1 高等数学）的出边表尾部插入一条指向课程 15 的边”。参数顺序记反了，边就全变成反向，而且不报错。

/* 尾插一条边：index 是起点下标（0 起），x 是终点编号（1 起） */ pGraphList initEdgeList(pGraphList pList, int x, int index) { pEdgeNode p1, p2; pVertexNode p3 = pList->vertex[index]; p1 = (pEdgeNode)malloc(sizeof(struct edgeNode)); if (p1 == NULL) { printf("Out of space!\n"); return pList; } p1->index = x; 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; }

一个顶点如果有 6 条出边，就要调用 6 次这个函数，每次都是从头走到尾。31 个顶点、30 条边，总代价可以忽略，但如果哪天课程规模扩到几百门，这个尾插就变成 O(出度²)，那时候加点辅助尾指针是必要的优化。当前规模下，可读性优先。

5. 避坑与排查：这套源程序最容易翻车的五个地方

代码不长，坑不少。下面五条都是这类课设里反复出现的问题，每条按“看到什么现象 → 为什么 → 怎么改”来说，照着排查能省掉大半天。

5.1 结果数组跨函数传递后数据丢失

现象：拓扑排序函数内部打印结果是对的，一返回主函数再打印，前面几个还在，后面的变成乱码或者直接消失。同一份代码在不同编译器下表现还不一样，有的能显示二十多个，有的只显示两个。

原因：排序结果存在函数内的局部数组里，函数结束后把数组名（本质是首地址）返回给主函数。局部数组在栈上，函数一返回，那块栈空间就被回收了，主函数拿到的是一个悬垂指针，读到什么全看运气。栈上内容什么时候被覆盖、覆盖多少，跟编译器的栈帧布局有关，所以不同环境下表现不同，这种不确定性最耗时间。

解决：把结果数组改成全局数组int pTopo[31];，排序函数直接往里写，主函数直接读。课程设计规模小，全局变量带来的耦合代价远小于调试成本，这是合理的工程取舍。如果不想用全局变量，正确做法是由调用方分配数组、把指针作为参数传进去，而不是返回局部数组。

5.2 顶点编号从 1 开始引发的下标错位

现象：程序能跑完，输出 31 行也不缺，但课程顺序怎么调都不对，删掉某条边重跑，变化又莫名其妙。加打印看入度，和手算的表对不上。

原因：课程编号习惯从 1 开始（1 到 31），数组下标从 0 开始（0 到 30）。代码里有的地方减了 1，有的地方忘了减，还有的地方减了两次。最典型的是vertex[element]和vertex[element - 1]混用，前者访问的是下一门课，后者才是当前课，症状表现为“整体偏移一位”。

解决：定一条死规矩——凡是“课程编号”出现的地方，用在数组下标上必须减一；编号本身只用于输出和队列存取。定完规矩之后，把所有vertex[...]的地方过一遍，逐一确认。这个坑我一般靠单步跟踪定位：盯着element的值和vertex[element-1]->vertexInfo是否相等，不相等就是这里错了。

5.3 边的方向录反导致入度全乱

现象：程序不崩溃、不报环，输出 31 门课一个不少，但第一学期开的全是本该最后一学期上的课。入度表里基础课入度变成 2 或 3，后续课入度变成 0。

原因：initEdgeList(pList, x, index)的两个参数搞反，把“起点下标”和“终点编号”写颠倒了，于是所有边都反向。因为反向之后图仍然是无环的（原来是 A→B，反了是 B→A，环结构不变），所以环检测也发现不了。

解决：录完边之后先打印一张出边表，挑三门基础课核对。高等数学的出边应该是 15 和 28；C 语言程序设计的出边应该是 8、9、10、24、28、30；电路理论的出边应该是 6。三条对上，基本可以确认方向没反。这三条对不上，后面怎么调都是白费。

5.4 环检测被忽略，输出静默缺课

现象：输出只有二十几行，少了若干门课，程序没有报任何错误，退出码也是 0。

原因：边表里出现了回路，比如课程 11 指向 13、13 又指回 11，这两门课的入度互相扣着，永远减不到 0，永远进不了队列。主循环正常结束，只是定稿数量少于 31。如果没写n < pList->n那段判断，程序会安静地输出一个残缺结果。

解决：环检测那三行必须保留，并且报错信息要写清楚是环，不要只打印一句“error”。定位环的办法是打印所有入度不为 0 的顶点编号——正常情况下跑完之后所有入度都应该是 0，剩下不为 0 的那批顶点就处在环上，从它们出发顺着出边表走一圈就能找到具体是哪条边录错了。

5.5 测试截图与实际输出不一致

现象：交上去的运行截图里，最后几门课里有一门重复出现了两次，导师一眼看出来，问是不是算法写错了。

原因：截图时终端内容超出一屏，滚动鼠标翻页，两次截图的交界处有重叠行，拼起来就多了一行。算法本身没问题，是记录方式出的问题。

解决：截图前先把输出重定向到文件，program > result.txt，再打开文件截图，或者直接把结果贴进文档。同时加一条自检逻辑：跑完之后统计每门课的出现次数，全部为 1 才算通过。这条检查比人眼数 31 行可靠得多，也是我后来每次交付前必跑的一步。

6. 验收与答辩：怎么证明这份教学计划排对了

排出来一串看着合理的顺序，不等于方案站得住。验收要做的是把“看起来对”变成“逐条可查”，答辩要做的是让评审在三分钟内确认这件事。

验收我一般按三个层次走。第一层查数据完整性：顶点必须正好 31 个，编号 1 到 31 无缺无重，输出行数等于 31，每门课出现次数为 1。第二层查图的正确性：逐顶点打印出边表，和培养方案的先修表逐条对照；打印入度数组，和手算表比对，比如数值分析入度 3、数据结构入度 1、嵌入式系统入度 2、人工智能入度 2，这几门对上，说明边表和反算逻辑都没问题。第三层查序列合法性：遍历所有边，验证起点在序列中的位置严格小于终点位置，这是拓扑序的数学定义，一条都不能破。

答辩时最常被追问的是复杂度和选型。复杂度答 O(n+e)：初始化入度和主循环各扫一遍边表，每个顶点入队一次、每条边被检查一次，n 是 31、e 是 30，实际运行几乎是瞬时的。选型答两点：邻接表而不是邻接矩阵，是因为图稀疏，矩阵会把遍历退化成 O(n²)；广度优先而不是深度优先，是因为深搜会把可以并行的课程拉成串行，排出来的计划不符合教学规律，这一点最好现场举 C 语言、数据结构、算法设计与分析这条链被拉长、高等数学被推到后面的例子，比空讲概念有说服力。

还有一问几乎必来：为什么用全局数组存结果。别绕，直接讲局部数组返回后栈空间被回收、数据丢失的现象和原因，再说明这是规模小场景下的合理取舍，同时给出替代方案——由调用方传数组指针进来。能把自己的坑讲清楚，比讲一堆原理更让人信服。

从那以后我每次交这类图算法作业，都强制走一遍“边表回查加出现次数统计”，不管代码看着多顺眼。翻车往往不是因为算法难，而是因为那几个减一、那几个参数顺序，混在几百行里根本看不出来。希望帮到你。

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