图论习题解析：度数、连通性与遍历

"本资源为严蔚敏版数据结构教材中第6章关于图的习题解答，包含选择题，涉及图的度数性质、有向图与无向图的边数计算、连通图的概念、邻接矩阵的应用、非连通无向图的顶点数量、深度优先搜索（DFS）与广度优先搜索（BFS）以及最小生成树的构造算法等知识点。" 详细知识点说明： 1. **图的度数性质**：在一个无向图中，所有顶点的度数之和等于边数的2倍。这是因为每条边连接两个顶点，贡献了两个度数。而在有向图中，所有顶点的入度之和等于所有顶点的出度之和，这是因为每条有向边增加了一个出度和一个入度。 2. **有向图的边数**：具有n个顶点的有向图最多有n(n-1)条边，因为每条边是从一个顶点指向另一个顶点的有序对。 3. **连通图的性质**：如果一个无向图是连通的，那么从任一顶点出发都能到达其他所有顶点。当用邻接矩阵表示连通图时，至少有2(n-1)个非零元素，表示至少有n-1条边保证图的连通性。 4. **非连通无向图的顶点数量**：一个有28条边的非连通无向图至少需要9个顶点，因为8个顶点的完全图有28条边，但这里是非连通的，所以至少需要9个顶点。 5. **深度优先搜索（DFS）与广度优先搜索（BFS）**：DFS适用于发现图中的所有路径，通常使用栈作为辅助数据结构；而BFS用于寻找最短路径或构造BFS树，通常使用队列。 6. **最小生成树的构建算法**：Prim算法适合于稠密图，而Kruskal算法适用于稀疏图。Floyd算法用于求解最短路径问题，Dijkstra算法同样用于最短路径问题，但不适用于带负权的图。 7. **二叉树遍历与图遍历的类比**：深度优先遍历类似于二叉树的先序遍历，而广度优先遍历类似于二叉树的层次遍历。 8. **BFS与DFS生成树的高度比较**：BFS生成树的树高可能等于或小于DFS生成树的树高，这取决于图的具体结构。 这些习题涵盖了图论基础、图的遍历策略以及最小生成树的构建方法等多个核心概念，对于理解和掌握图的算法设计至关重要。通过这些题目，学习者可以加深对图的理论和实践应用的理解。