AOV/AOE网图处理：邻接表实现与关键路径探索

本实验旨在通过实际编程操作加深对图论中关键概念的理解，包括拓扑排序、关键路径、最小生成树和最短路径。实验内容涉及两种类型的图——AOV网（Activity On Vertex，活动-顶点网络）和AOE网（Activity On Edge，活动-边网络）。 首先，实验要求学生独立完成两个题目： 1. **AOV网的实现**：在这个题目中，学生需要从键盘输入AOV网的顶点和有向边信息，构建邻接表存储结构。邻接表是图的一种常用存储方式，它用一个数组（AdjList）表示每个顶点的所有出边，每个节点（ArcNode）包含指向下一个出边节点的指针。学生需设计并实现AOV网的类型定义，包括VNode（顶点节点）和ALGraph（邻接列表图），同时实现基本操作如添加顶点和边，以及进行拓扑排序。教材图7.28提供了测试数据。 拓扑排序是按特定顺序访问图中的顶点，确保对于每条有向边（u->v），顶点u总是在顶点v之前被访问。算法的关键在于维护一个拓扑排序序列，通常借助栈来辅助，先遍历入度为0的顶点，然后递归地处理它们的邻居，直到所有顶点都被处理。 2. **AOE网的关键路径计算**：对于AOE网，学生需要继续从键盘输入顶点和有向边信息，同样构建邻接表。不同于AOV网，这个题目要求找出网络中的关键路径，即耗时最长的一条路径，以及关键路径的长度。关键路径的寻找涉及到最短路径算法的变种，可能需要用到Dijkstra算法或更复杂的方法，如深度优先搜索（DFS）或广度优先搜索（BFS）配合优先队列来辅助查找。 实验中还涉及到图的存储结构定义，如ArcNode用于表示有向边，VNode表示顶点，以及SqStack结构用于辅助拓扑排序过程。此外，还要求学生处理栈的操作，如初始化、元素的压入（Push）和空间动态分配。 通过这些实践性任务，学生不仅可以巩固图的存储结构，还能提高对图算法的实际应用能力，如数据结构的设计、基本操作实现和解决典型问题的能力。最后，测试数据的使用确保了学生在解决实际问题时能正确运用所学知识。