如何用Prolog无列表实现无环有向图所有路径的正序输出？

我来帮你搞定这个路径逆序输出的问题！

问题原因分析 #

你当前的代码之所以会输出逆序路径，是因为递归的执行顺序导致的：程序会先递归深入到终点节点，回溯的时候才依次写入当前节点。比如找a到f的路径时，程序先走到f并输出它，接着回溯到e输出e，再到c输出c，最后回到a输出a，结果就变成了feca。

解决方案（无需使用列表） #

我们只需要调整write的执行时机，在递归前进的过程中就输出当前节点，而不是等到回溯时再写。修改后的代码如下：

edge(a, c). 
edge(a, d). 
edge(c, e). 
edge(e, f). 
edge(d, f). 

paths(Curr, Stop) :-
    Curr == Stop,
    write(Curr).  % 到达终点时直接输出
paths(Curr, Stop) :-
    Curr \== Stop,
    write(Curr),  % 先输出当前节点，再递归探索下一个节点
    edge(Curr, Next),
    paths(Next, Stop).

测试效果 #

执行paths(a,f).后，会先输出aceftrue，回溯后输出第二个解adftrue。如果想让路径和Prolog的true输出更清晰，可以在终点输出后添加换行：

paths(Curr, Stop) :-
    Curr == Stop,
    write(Curr), nl.  % 输出终点后换行
paths(Curr, Stop) :-
    Curr \== Stop,
    write(Curr),
    edge(Curr, Next),
    paths(Next, Stop).

此时输出会变成：

acef
true ;
adf
true .

这个写法完全不需要用列表存储路径，通过调整输出时机实现了正序路径的打印，完美符合你的需求～

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