【数据结构】图的遍历、图的应用

以下是对王道数据结构图的部分选择题的纠错

图的遍历

对于一个非连通无向图G，采用DFS访问所有顶点，在DFSTraverse函数中调用DFS的次数正好等于连通分量个数

一次遍历必然会将一个连通图中的所有顶点都访问到，对于已被访问的顶点不在调用DFS，计算连通分量时可以统计DFSTraverse函数中调用DFS的次数
2.（C）

对于无向图来说，在DFS过程中遇到了回边，肯定遇到了环
对于有向图来说
3.（A）

等后面学了拓扑排序再说

4.（D）

图的应用

用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树可能相同，可能不同

注意当无向连通图的最小生成树唯一时，不同算法生成的最小生成树必定是相同的
6.（A）

7.（D）

顶点数大于1的回路，构成强连通分量
8.（C）

枚举法，有点懒得列举，会做其他题目即可，烦
9.（C）

• 有向图的邻接矩阵第V行1的个数只能表示该顶点的出度，但是有向图的度=出度+入度
• 有向图的邻接矩阵不一定是非对称矩阵
• 最小生成树中的所有边不一定就是权值最小的，因为有的权值小的边不一定能使图连通
• 有时候不同的有向无环图的拓扑排序序列是一样的

10.（A）

最小生成树有时候不止一棵
11.（B）

要缩短工程的工期，需要关键活动上的所有活动都缩短时间，但是但凡增加一个关键活动的时间，总的工期就延长了。