在一个无权图中,从起始节点到目标节点的最短路径必须经过k个节点,且图中存在环路,以下哪种算法最适合寻找满足条件的路径?
答案解析
A选项错误,BFS只能找到最短路径,但不能保证经过特定数量的节点。B选项错误,DFS深度限制为k+1,只能保证路径长度不大于k+1,无法保证恰好经过k个节点,并且在存在环的情况下可能陷入无限循环,即使不陷入循环也可能重复访问节点;C选项错误,先用BFS找到最短路径,不能保证该最短路径经过k个节点,并且用DFS进行验证也存在效率问题;D选项正确,改进的BFS算法通过记录路径长度并判断,可以在保证找到路径的同时筛选符合长度要求的路径,有效地解决了该问题,且在发现路径长度不符合k+1要求时,可以进行剪枝,从而更高效的找到符合条件的路径。需要注意的是,路径经过k个节点,意味着需要k+1个顶点,因此需要寻找长度为k+1的路径。
正确答案:D