数据结构有向图习题：判断下列选项中的无效路径

题目 #

针对上图的有向图，以下选项中哪项是无效路径？

• A. CBA
• B. CDEFG
• C. CDACBA
• D. CDA

解答 #

首先明确有向图路径的基本规则：路径是由顶点组成的序列，序列中相邻的前后两个顶点，必须存在从前一个顶点指向后一个顶点的有向边才算合法。如果题目考查的是简单路径（数据结构中图部分的选择题默认考查简单路径的概率更高），还额外要求路径中所有顶点不能重复出现。

先列出该图全部有效有向边，方便逐一核对：

• C的出边：C→B、C→D
• B的出边：B→A
• A的出边：A→C
• D的出边：D→A、D→E
• E的出边：E→F
• F的出边：F→G

逐一分析选项：

1. 选项A CBA：序列对应路径C→B→A，两条边都真实存在，且无重复顶点，是有效路径。
2. 选项B CDEFG：序列对应路径C→D→E→F→G，四条边都真实存在，且无重复顶点，是有效路径。
3. 选项C CDACBA：序列对应路径C→D→A→C→B→A，所有边都真实存在，符合普通路径的要求；但路径中C、A两个顶点各出现了2次，不符合简单路径的要求，属于无效简单路径。
4. 选项D CDA：序列对应路径C→D→A，两条边都真实存在，且无重复顶点，是有效路径。

综上，如果题目考查的是简单路径，答案为选项C。

内容的提问来源于stack exchange，提问作者Nguyễn Thế Hồng Hạnh