《数据结构》第六章：图的概述与基本概念详解

本资源是一份详细的数据结构与应用笔记，主要涵盖了第六章关于图的数据结构相关内容。章节内容涉及了填空题、判断题、单项选择题，以及对图的基本概念、性质和算法的深入理解。 1. 填空题部分： - **AOV-网**：这是一种将顶点表示活动，用弧表示活动间优先关系的有向图。 - **无向完全图**：拥有n(n-1)/2条边的无向图，每个顶点与其他所有顶点都相连。 - **有向完全图**：拥有n(n-1)条边的有向图，每对顶点之间都有箭头连接。 - **完全无向图中最大边数**：对于n个顶点的图，最大边数为n(n-1)/2。 2. 判断题： - 无向图不一定存在生成树，因为生成树需满足特定条件（如连通且无环）。 - 连通分量是无向图中的最小连通子图，而不是极小。 - 强连通分量是连通且可以从任何顶点到达其他所有顶点的有向图子集。 - 邻接矩阵存储空间大小与顶点数有关，与边数无关，但实际存储可能要考虑稀疏性。 - 邻接表更适合表示有向图，邻接矩阵适用于无向图和有向图。 - Prim算法在边较少、结点较多时效率较低，更适合稠密图。 - 最小生成树的形状可能因图的具体结构而不同，不唯一。 - AOV网的拓扑序列由于活动的顺序依赖于活动间的依赖关系，可能不是唯一的。 - AOE网存在环时无法进行拓扑排序，反之则可以。 - 拓扑排序确保活动按顺序执行，但不一定影响工程总工期。 3. 单项选择题： - 所有顶点度数之和等于边数的2倍，因为每条边连接两个顶点。 - 有向图中入度和出度之和相等，所以为1倍。 - 有向图最多边数为n(n-1)，选择项B正确。 - 连通图的邻接矩阵至少有2(n-1)个非零元素，因为每对连通顶点至少有一条边。 - 非连通无向图至少有9个顶点，以保证28条边的存在。 这些题目涵盖了图的定义、分类、度量、存储表示方法、搜索算法以及关键路径分析等核心知识点，对于学习和复习数据结构中的图论部分非常有帮助。通过解答这些问题，学生可以深化对图的概念、算法和应用的理解。