数据结构 第六章 图 练习题及答案详细解析.pdf

【知识点详解】 1. 图的基本概念： - 图是由顶点和边构成的数据结构，用于表示顶点之间的关系。 - 无向图中的边没有方向，每条边连接两个顶点；有向图的边有方向，从一个顶点指向另一个顶点。 2. 图的边数范围： - 无向图中，顶点数为 n 时，最少有 0 条边（空图），最多有 n(n-1)/2 条边（完全图）。 - 有向图中，最少也有 0 条边（空图），最多有 n(n-1) 条边（完全有向图）。 3. 连通分量： - 在图中，如果任意两个顶点都是连通的，即存在路径相连，那么这个图是连通图，连通图的连通分量就是其本身。 4. 图的存储结构： - 邻接矩阵：用二维数组存储图中每个顶点的邻接点。 - 邻接表：为每个顶点维护一个链表，链表中的节点代表与该顶点相邻的其他顶点。 5. 空间复杂度： - 无向图的邻接表表示空间复杂度为 O(n+e)，因为每个顶点在顶点表中占一个节点，每条边在边表中占两个节点。 6. 入度和出度： - 在有向图中，第 j 个顶点的入度是其邻接矩阵第 j 列所有元素之和。 - 第 i 行的所有元素之和等于顶点 i 的出度。 7. 遍历方法： - 深度优先遍历类似树的前序遍历，使用栈作为辅助数据结构。 - 广度优先遍历类似树的层序遍历，使用队列作为辅助数据结构。 8. 最小生成树算法： - Prim 算法求最小生成树的时间复杂度为 O(n^2)，适用于稠密图。 - Kruskal 算法的时间复杂度为 O(e log e)，适用于稀疏图。 9. 拓扑排序： - 若有向图不存在回路，则可得到一个拓扑序列，顶点按出现顺序排列。 - 在拓扑排序中，如果存在弧 vi->vj->vk，则 vi 必须在 vj 之前，vj 必须在 vk 之前。 10. 度数性质： - 无向图所有顶点的度数之和等于边数的两倍（握手定理）。 11. 强连通图： - 强连通图是每个顶点都能通过有向边到达其他所有顶点的有向图，至少含有 n 条边，形状为环状。 12. 生成树： - 生成树是无环且连通的子图，包含原图的所有顶点，但不一定唯一。 - n 个顶点的无向图的生成树有 n-1 条边。 13. 判断有向图是否存在回路： - 可以使用深度优先遍历，若遍历过程中形成环，则存在回路。 14. 关键路径与工程计划： - 关键路径决定工程完成时间，关键活动的延迟会影响整体工程进度。 - 如果所有关键活动都提前完成，整个工程会提前完成。 - 单个关键活动提前完成并不一定意味着整个工程提前完成，除非它是唯一的路径。 以上是针对给定题目中涉及的图论知识的详细解释。