题2
题目
Q:a下列关于图的说法中, 错误的是 ( ).
I. 对一个无向图进行深度优先遍历时, 得到的深度优先遍历序列是唯一的
II. 若有向图不存在回路, 即使不用访问标志位, 同一结点也不会被访问两次
III. 采用深度优先遍历或拓排排序算法可以判断一个有向图中是否有环 (回路)
IV. 对任何非强连通图必须 2 次或以上调用广度优先遍历算法才可访问所有的顶点
A. I、II、III
B. II. III
C. I、 II
D. I、 II、IV
分析
A:无论是深度优先还是广度优先，遍历的结构都取决于图的存储方式，如果图的存储方式不唯一，那么两者都不唯一
我觉得1和2和3都是错的
什么是非强连通图？如果一个有向图的任意两个顶点之间都存在路径，那么这个有向图就是强连通图，否则就是非强连通图
解
D
图的深度优先遍历序列通常是不唯一的, I 错误。图 1 是一个不存在回路的有向图, 从顶点 1 开始执行广度优先遍历, 若不设置访问标志位, 则会重复访问顶点 3, II 错误。
深度优先遍历 (见本节后面习题的解析) 或拓扑排序算法可以判断有向图中是否有环, III 正确。
图 2 是一个非强连通图, 但从顶点 1 开始调用一次广度优先遍历算法就可访问所有顶点, IV 错误。