无向图

Question

如何找到无向图的终点？

Graph :

    Node : S, Y, F, T                visualization :    S ----- Y ---- T
    Edge : S --- Y                                       \     /
           Y --- F                                        \   /
           S --- F                                         \ /
           Y --- T                                          F


Assume that

       Start   S 
       Finish  F

       after run   go 

       result will be :

              S F
              S Y F

我不想多次访问一个节点。如果访问，此问题将成为NP问题之一。

编辑：

输入可以是任何形式

example:

       edge (S,Y).     OR          edge (Y,S).
       edge (Y,F).                 edge (F,Y).
       edge (S,F).                 edge (F,S).
       edge (Y,T).                 edge (T,Y).

但输出必须相同

Answer 1

跟踪访问的节点，并在下一步中添加可能的目的地时将其排除。

我更改了一些边并添加了一条边，以确保当边以从S到F的“错误”顺序列出边时，它也可以使用。

edge('S','Y').    visualization:    S -- Y -- T
edge('F','Y').                     / \  /
edge('S','F').                    /   \/
edge('Y','T').                   A --- F
edge('A','S').
edge('F','A').

在序言中，它应该大致如下所示：

pathBetween(A,A,_):- !, fail.
pathBetween(S,F,Visited) :- (edge(S,F) ; edge(F,S)),
    append(Visited,[S,F],L),
    write(L).
pathBetween(S,F,Visited) :-
    (   edge(S,A) ; edge(A,S)  ),
    not(member(A,Visited)),
    pathBetween(A,F,[S|Visited]).

您可以使用;手动找到所有解决方案，或findall。

?- findall(Visited, pathBetween('S', 'F', []), _).
[S,F][S,Y,F][S,A,F]
true.