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

在数据结构中，图是一种重要的非线性数据结构，由顶点和边组成。图可以是有向的，也可以是无向的，根据题目内容，我们将深入探讨以下几个知识点： 1. **图的基本概念**： - **度数**：在无向图中，一个顶点的度是与该顶点相连的边的数量。所有顶点的度数之和等于边数的两倍，因为每条边连接两个顶点，所以选项2正确。 - **连通图与生成树**：无向连通图是指图中任意两个顶点都可通过边相连。最小生成树是连通图中边的子集，使得这些边形成一棵树且包括所有顶点，且权重最小。对于无向连通图，最小生成树只有一棵，选项A正确。 - **入度与出度**：在有向图中，顶点的入度是进入该顶点的边数，出度是离开该顶点的边数。所有顶点的入度之和等于出度之和，因为每条有向边都贡献一次入度和一次出度，所以选项B正确。 2. **图的边数计算**： - 一个有 n 个顶点的无向图最多有 n*(n-1)/2 条边，因为每对不同的顶点之间至多有一条边，选项C正确。 - 具有 4 个顶点的无向完全图有 6 条边，因为每个顶点与其他三个顶点都相连，选项A正确。 - 要确保一个有 6 个顶点的无向图连通，最少需要 5 条边（形成树形结构），选项A正确。 - 要连通全部 n 个顶点的无向图至少需要 n-1 条边，选项C正确。 3. **邻接矩阵与邻接表**： - 邻接矩阵用于表示图，是 n*n 的矩阵，如果无向图中 (i,j) 有边，则 A[i][j] = A[j][i] = 1，否则为 0。所以，空2的答案是1，空3的答案也是1。 - 邻接表是另一种存储图的方式，对于有 n 个顶点的无向图，表头向量大小为 n，所有邻接表中的节点总数是边数的两倍，因为每条边在邻接表中会被表示两次，所以空1的答案是2e，空2的答案是2e。 4. **图的遍历**： - 深度优先搜索（DFS）和宽度优先搜索（BFS）是遍历图的两种主要方法。DFS 可以产生不同的顶点序列，例如题目中的①可以是 aebcfd 或 acebfd 等，而 BFS 总是从起点开始逐层扩展，所以②可能是 a,b,c,e,f,d。 - 题目12中，DFS 和 BFS 对于邻接表存储的图与二叉树的遍历方式类似，DFS 类似于二叉树的先序遍历，BFS 类似于二叉树的按层遍历。 5. **图的其他性质与应用**： - 判定有向图是否存在回路可以使用深度优先遍历，若在遍历过程中发现回路，则存在回路。 - 关键路径是事件结点网络中最长的路径，它决定了项目的最短完成时间。 - 在AOE网（活动-on-edge图）中，关键活动的权值之和等于工程的工期，而减少关键活动的权值不一定能减少工期。 6. **拓扑排序**： - 拓扑排序是对有向无环图（DAG）的顶点的一种排序，使得对每一条有向边 (u, v)，顶点 u 都在顶点 v 之前。题目18中，图7.3的拓扑排序结果是125634。 7. **连通分量**： - 对于有 n 个顶点的无向连通图，其连通分量个数为1，因为所有顶点都是连通的。 8. **邻接表与逆邻接表**： - 一个顶点在邻接表中的单链表长度等于其出度，在逆邻接表中的单链表长度等于其入度。 以上内容涵盖了图的度数性质、边数计算、存储结构、遍历方法、拓扑排序以及连通性等相关知识点。通过理解这些概念，我们可以有效地操作和分析图数据结构。