问题
单项选择题
下列关于图的叙述中正确的是______。
Ⅰ.回路是简单路径
Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间
Ⅲ.若有向图中存在拓扑序列,则该图不存在回路
A.仅Ⅰ
B.仅Ⅰ,Ⅱ
C.仅Ⅲ
D.仅Ⅰ,Ⅲ
答案
参考答案:C
解析: Ⅰ.几个概念的描述如下:
回路:第一个顶点和最后一个顶点相同的路径称为回路(环)。
简单路径:在一条路径中,若没有重复相同的顶点,该路径称为简单路径。
简单回路:在一个回路中,若除第一个与最后一个顶点外,其余顶点不重复出现的回路称为简单回路(简单环)。回路对应于路径,简单回路对应于简单路径。
Ⅱ.存储稀疏图时,使用邻接表比邻接矩阵更省空间。
Ⅲ.若有向图中存在拓扑序列,则说明该图不存在回路。
通过以上分析可知只有Ⅲ的描述是正确的。