图论实验：数据结构中的深度优先与广度优先搜索，最小生成树与拓扑排序

本实验旨在通过实践操作加深对图论数据结构的理解，重点涵盖以下几个方面： 1. **图的表示**：实验要求学生掌握用邻接矩阵和邻接表两种方式来描述图。邻接矩阵是一种二维数组，其中行和列表示图中顶点，元素值表示两个顶点之间是否存在边及其权重。邻接表则以链表形式存储，每个顶点对应一个链表，链表中的节点包含相邻顶点的信息。这里涉及自定义字符作为顶点，用于展示实际应用中的灵活性。 2. **图的遍历**：实验中包括深度优先搜索 (DFS) 和广度优先搜索 (BFS) 的实现。DFS从选定的起始顶点开始，尽可能深地探索图，直至无法继续为止，然后回溯。BFS则按层次顺序遍历，先访问距离起点最近的节点。这两种方法是图论中的基本操作，对于查找路径、连通性等问题至关重要。 3. **最小生成树算法**：实验要求实现Prim算法或Kruskal算法之一来构建无向图的最小生成树。Prim算法是从一个初始顶点开始，每次添加与当前树相连且与未加入顶点间边权最小的边，直到所有顶点都加入。Kruskal算法则是将所有边按照权重排序，依次加入，每次选择不形成环的最小边。 4. **拓扑排序**：针对AOV网（活动-对象-价值网络），实验涉及到拓扑排序的实施。拓扑排序是根据网络中依赖关系，对活动进行排序，使得依赖关系满足“有向无环”的条件。步骤包括选择入度为0的顶点并输出，然后删除与之相关的边，重复此过程直到所有顶点处理完毕。 5. **关键路径**：在AOE网（活动-时间-资源网络）中，关键路径是指从起点到终点的最长路径，它决定了整个项目的最短完成时间。实验提供了`ch7_critical_path.c`文件，可能包含关键路径算法的具体实现，如 Earliest Start Time (EST) 或 Latest Finish Time (LFT) 方法。 通过这个实验，学生不仅能巩固图的概念，还能提升算法设计和编程能力，尤其是在实际问题中运用数据结构解决复杂网络问题的能力。实验中的四个部分相互关联，共同构建了图论知识体系的完整性，为后续深入研究打下坚实基础。