数据结构第7章图习题.pdf

数据结构中的图是一种重要的抽象数据类型，用于表示实体之间的关系。本章主要涉及与图相关的概念和算法，包括图的性质、表示方法以及遍历策略。 1. 在一个无向图 G 中，所有顶点的度数之和等于所有边数之和的2倍。因为无向图的每条边连接两个顶点，所以每条边会为两个顶点的度数各增加1，所以总度数是边数的两倍。 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。这是因为在有向图中，每条边有一个起点和一个终点，起点的出度增加1，终点的入度增加1，所以入度之和等于出度之和。 3. 一个具有 n 个顶点的无向图最多包含 n(n-1)/2 条边。这是无向完全图的情况，每个顶点与其他所有顶点都有一条边相连。 4. 一个具有 n 个顶点的无向完全图包含 n(n-1)/2 条边，与第3题解释相同。 5. 一个具有 n 个顶点的有向完全图包含 n(n-1) 条边。每个顶点指向其他所有顶点，因此每对不同的顶点之间有两条边（一条去向，一条返回）。 6. 对于具有 n 个顶点的图，若采用邻接矩阵表示，该矩阵的大小为 n×n，因为每个顶点对应矩阵中的一行和一列。 7. 无向图的邻接矩阵是对称矩阵，因为无向图中的边是双向的。 8. 对于一个具有 n 个顶点和 e 条边的无(有)向图，若采用邻接表表示，表头向量的大小为 n，因为每个顶点都有一个表头。 9. 同样，对于无(有)向图，采用邻接表表示时，所有顶点邻接表中的结点总数为 e，因为每条边对应邻接表中的一个节点。 10. 在有向图的邻接表中，每个顶点邻接表着该顶点的所有出边邻接点。 11. 在有向图的逆邻接表中，每个顶点邻接表着该顶点的所有入边邻接点。 12. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，说明图是连通图。 13. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历，首先访问根节点，然后遍历其子节点。 14. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的按层遍历，逐层访问节点。 15. 如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点，说明 G 有两个连通分量。 16. 非连通图可以使用深度优先搜索，只是每次搜索只能遍历一个连通分量。 17. 有向图的遍历可以采用广度优先搜索方法，例如生成树的构造。 18. 深度优先搜索从 v1 出发，按照 v1->v2->v4->v5->v3 的顺序访问。 19. 从顶点 1 开始进行深度优先遍历，可得到顶点访问序列为 1，2，4，3，5，7，6。 20. 广度优先遍历从顶点 1 开始，可得到顶点访问序列为 1，2，4，3，5，6，7。 21. 一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图，即没有环且包含所有顶点。 22. 若 G' 为 G 的生成树，则 G' 是 G 的子图，无环且连通，但不一定是极小连通子图，因为 V' 可能不等于 V。 23. 无向连通图有一棵或多棵最小生成树，取决于边的权重。 24. 最小生成树是指图中任意一个使得所有边权重之和最小的树形子图，保证了连通性。 这些知识点涵盖了图的基本概念、表示方法（邻接矩阵和邻接表）、遍历算法（深度优先搜索和广度优先搜索）以及生成树的概念。学习这些内容对于理解和操作图数据结构至关重要。