"数据结构第8章：图的基本概念、存储结构、遍历与应用"

数据结构的第8章主要讨论了图这一数据结构的基本概念、存储结构、遍历、生成树和最小生成树、最短路径、拓扑排序、AOE 网与关键路径等内容。图是由顶点的有限集合 V(Vertex)和连接这些顶点的边的有限集合 E(Edge)组成的，记为 G=(V,E)。其中，如果代表边的顶点对是无序的，则称为无向图，而如果表示边的顶点对是有序的，则称为有向图。 在图中，存在一些基本的术语，如端点和邻接点。在一个无向图中，如果存在一条边 (vi,vj)，则称 vi 和 vj 为此边的两个端点。对于一个顶点 vi，如果存在一条边 (vi,vj)，则称顶点 vj 是顶点 vi 的邻接点。 图的存储结构是指在计算机中如何高效地存储图的结构和边的信息。常用的存储结构包括邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中数组元素表示图中的边是否存在；而邻接表是一种链表的形式，用于表示图中每个顶点的邻接点。 图的遍历是指从图中的某一个顶点出发，访问图中的所有其他顶点。常用的遍历方法包括深度优先搜索（DFS）和广度优先搜索（BFS）。在遍历的过程中，通常需要借助栈或队列来实现。 生成树是指一个无向连通图的一个子图，它包含图中所有的顶点，但只包含足以构成一棵树的 n-1 条边。最小生成树则是在一个带权无向连通图中的一棵权值最小的生成树。 最短路径是指图中两个顶点之间经过的边的权值之和最小的路径。常用的最短路径算法包括 Dijkstra 算法和 Floyd 算法，它们分别适用于不含负权边的图和含有负权边的图。 拓扑排序是对有向无环图中所有顶点的一种线性次序，使得若图中存在一条从顶点 vi 到 vj 的路径，则在拓扑排序中顶点 vi 必定排在顶点 vj 的前面。 AOE 网与关键路径是指一种用图来表示工程项目中活动与活动之间的关系的方法。关键路径是指在工程项目中不能延误的活动的集合，它决定了整个工程项目的最短完成时间。 总之，图作为一种重要的数据结构，在计算机领域有着广泛的应用。掌握图的基本概念、存储结构、遍历、生成树和最小生成树、最短路径、拓扑排序、AOE 网与关键路径等内容，对于理解和应用图这一数据结构非常重要。