SWI-Prolog查询可到达指定终点的所有起点及重复问题解决

错误原因 #

1. 最初版本未处理图中的循环路径，也没有排除起点与终点重合的无效结果，递归时会在环（如0→1→2→0、3→4→3）上无限遍历，导致重复输出X=0的无效结果，甚至栈溢出。
2. 修改后的版本仅添加了X\==Y校验，既没有解决循环遍历的核心问题，校验逻辑也限制了长路径的递归查询，因此仅返回X=2就停止，查询3、4到0的路径时依然会触发无限递归栈溢出。

正确实现方案 #

核心解决思路是新增参数记录已经访问过的节点，每次遍历时跳过已访问节点，从根源上避免走环，同时强制排除起点等于终点的无效结果。
实现代码如下：

% 对外暴露的查询接口
go(X, Y) :-
    travel(X, Y, [X]).

% 递归遍历逻辑，第三个参数为已访问节点列表
travel(X, Y, _) :-
    link(X, Y),
    X \== Y.
travel(X, Y, Visited) :-
    link(X, Z),
    X \== Y,
    \+ member(Z, Visited), % 跳过已访问节点，避免循环
    travel(Z, Y, [Z|Visited]).

测试效果 #

执行查询?- go(X, 0).，返回结果如下，无重复无死循环，符合预期：

X = 2 ;
X = 1 ;
X = 3 ;
X = 4 ;
false.

内容的提问来源于stack exchange，提问作者SwainG