下列关于图的叙述中,正确的是()
Ⅰ. 回路是简单路径
Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间
Ⅲ.若有向图中存在拓扑序列,则该图不存在回路
A.仅Ⅱ
B.仅Ⅰ、Ⅱ
C.仅Ⅲ
D.仅Ⅰ、Ⅲ
回路对应于路径,简单回路对应于简单路径
解答:C。Ⅰ.回路对应于路径,简单...
用户登录可进行刷题及查看答案
解答:C。Ⅰ.回路对应于路径,简单回路对应于简单路径;Ⅱ.刚好相反;Ⅲ.拓扑有序的必要条件。故选C。
回路也称环,是起点和终点相同的路径。简单路径是没有顶点重复的路径。回路最后有顶点重复,不可能是回路,I错误。
稀疏图是边相对于顶点少很多的情况,设顶点数为 n ,边数为 e ,用邻接矩阵存储空间为 O(n^2) ,用邻接表存储有向图存储空间为 O(n+e) ,无向图存储空间为 O(n+2e) ,明显存储稀疏图,用邻接表比邻接矩阵更省空间。II错误。
若有向图存在回路,则不存在拓扑序列,拓扑序列必须包含有向图中所有元素。III正确。
本题选C。
登录后提交答案