题目

下列关于图的叙述中，正确的是( )。

I. 回路是简单路径

II. 存储稀疏图，用邻接矩阵比邻接表更省空间

III. 若有向图中存在拓扑序列，则该图不存在回路

错因

A

把 II 当成对的。可能记反了——"稠密图用邻接矩阵省空间，稀疏图用邻接表"才是对的。邻接矩阵不论稀疏稠密都固定占 ，稀疏图时大量的 0 完全是浪费；邻接表只存实际存在的边，，稀疏时碾压邻接矩阵。

B

I 和 II 都误判为对。I 的关键：简单路径要求所有节点都不重复（含起点和终点）。回路的起点 = 终点是同一节点，违反"不重复"——回路不是简单路径，它是"简单回路"（除起终点外其他节点不重复的回路），两个概念别混。

D

I 误判为对（同 B），III 正确。所以选 D 的人核心错在 I——把"回路"当成"简单路径"了。

总解析

逐项判断：

• I 错：简单路径定义是路径上所有节点不重复（包括起点和终点）。回路起点 = 终点，违反"节点不重复"约束。回路最多算"简单回路"（除首尾外其他节点不重复），但不能直接称为"简单路径"。

• II 错：邻接矩阵固定 ，与边数无关；邻接表是 。

  • 稀疏图（）→ 邻接表占 远小于 ，邻接表更省
  • 稠密图（）→ 两者差距拉小，邻接矩阵的常数因子小反而可能略胜
  • 题目说反了。

• III 对：有向图存在拓扑序列 有向无环图（DAG）。如果有回路，回路上的所有节点彼此互为"前驱"，永远找不到入度为 0 的可起点，拓扑排序无法完成。

只有 III 正确。最终答案是 C。