🏷️ 知识点：简单路径

下列关于图的叙述中，正确的是（ ）。

Ⅰ. 回路是简单路径

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

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

图的概念

A. 仅 Ⅱ

B. 仅 Ⅰ、Ⅱ

C. 仅 Ⅲ

D. 仅 Ⅰ、Ⅲ

[tag_link]

正确答案：C

第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为 简单路径 ；简单回路除首尾顶点外不重复，但“简单路径”要求路径中的顶点不重复，所以回路不是简单路径，Ⅰ错误。稀疏图的边数远小于 n²，邻接矩阵固定占用 O(n²)，邻接表只占 O(n+e)，Ⅱ错误。存在拓扑序列等价于有向图无环，若 拓扑排序 输出结束后仍有顶点未输出，则剩余子图存在有向环。因此Ⅲ正确，仅Ⅲ正确，选 C。