如何用Prolog查找图中节点a到g的所有连通路径

你的现有代码仅能判断节点间是否连通，无法输出具体路径，还会因重复边产生重复结果，同时存在潜在循环风险。以下是改进方案：

问题分析 #

• 现有connected/2规则仅返回布尔值，不记录路径
• 数据库中重复的cites(a,c)会导致相同路径被多次返回
• 若图中存在环（比如假设d指向其他节点形成闭环），递归会陷入无限循环

改进代码 #

我们需要在规则中追踪已访问节点，避免循环，同时收集完整路径：

% 图的边定义（移除重复的cites(a,c)，避免重复路径）
cites(a,c).
cites(b,d).
cites(b,e).
cites(c,f).
cites(e,g).
cites(f,g).
cites(g,d).
cites(h,g).

% 基础情况：直接相连的两点构成路径
path(A, B, [A, B]) :- cites(A, B).

% 递归情况：经过中间节点的路径，确保不重复访问节点
path(A, B, [A|RestPath]) :-
    cites(A, C),
    C \= B,  % 避免与基础情况重复触发
    \+ member(C, [A]),  % 确保中间节点未被访问过
    path(C, B, RestPath),
    \+ member(A, RestPath).  % 二次校验，防止路径内出现重复节点

% 封装查询：获取a到g的所有去重路径
all_a_to_g_paths(Paths) :-
    findall(Path, path(a, g, Path), RawPaths),
    sort(RawPaths, Paths).  % 排序去重，消除重复结果

使用方法 #

在Prolog解释器中执行以下查询：

all_a_to_g_paths(Paths).

查询结果 #

你会得到所有从a到g的连通路径：

Paths = [[a,c,f,g]]

核心要点 #

• 路径收集：通过第三个参数[A|RestPath]逐步拼接完整路径
• 循环避免：利用member/2检查节点是否已在路径中，防止无限递归
• 去重处理：移除重复边+sort/2结果去重，确保每条路径仅返回一次

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