在无向图中,使用邻接表存储结构,判断顶点i到顶点j是否存在长度为k的简单路径。以下哪个选项正确描述了算法exist_path_len的核心逻辑?
答案解析
核心考点说明:本题考察的是对无向图中简单路径搜索算法的理解,特别是使用邻接表存储结构时的递归深度优先搜索(DFS)方法。
解题思路分析:算法exist_path_len通过递归地深度优先搜索来检查是否存在一条从顶点i到顶点j的简单路径,其长度恰好为k。在搜索过程中,通过标记已访问的顶点来避免重复访问,从而确保路径的简单性。
每个选项的详细分析:
A. 正确。算法通过DFS遍历图,确保路径长度为k且不重复访问顶点,符合题目要求。
B. 错误。算法使用的是DFS而非BFS,BFS不适用于此场景。
C. 错误。虽然算法使用了递归,但核心是DFS而非简单地检查所有可能的路径。
D. 错误。算法使用的是递归而非迭代方法。
易错点提醒:注意区分DFS和BFS的应用场景,以及递归与迭代的区别。
正确答案:A