使用Prolog进行图形循环检测

Question

我正在尝试编写一个Prolog程序，该程序可以检测无向图中的循环。我已经咨询了这个问题：prolog graph depth first search

并且已经尝试更改此处介绍的dfs算法，以检测周期。到目前为止，这是我的进度：

findCycle(Node, NextNode, Visited) :-
    (member(NextNode, Visited), isNotParent(Node, NextNode)) -> writeln("found a cycle"), saveCycle(Node, NextNode), !; writeln("end of findCycle").

saveCycle(Node, NextNode) :-
    % save to structure

dfs(Graph, StartNode) :-
    dfs(Graph, StartNode, []).

dfs(Graph, Node, Visited) :-
    writeln(Visited),
    \+ member(Node, Visited),
    write("visiting node "),
    write(Node), nl,
    member(NextNode, Graph.get(Node)),
    % \+ findCycle(Node, NextNode, Visited),
    dfs(Graph, NextNode, [Node|Visited]).

在我的实现中，图形将表示为字典，其中每个键都是一个顶点，而对应的值是其所有相邻顶点的列表。现在，我有一些问题：

• 我需要将每个顶点的“父级”存储在数据结构中，以便可以将其用于循环检测。我不确定该怎么做。到目前为止，我一直在用示例图来测试程序，该图的边缘是我用各个术语手动输入的。但是，那不是我的最终目标。

• 我还需要修复dfs算法，因为目前，由于Visited列表未持久存储所有顶点，它会导致堆栈溢出。理想情况下，Visited应该是字典而不是列表，这样可以更有效地访问它。

• 最后，如果检测到一个循环，我想将参与其中的所有顶点保存到另一个数据结构中。

尽管我了解编程，并且过去曾经用C ++编写过该程序，但是我对序言的掌握最多是基本的知识，因此对您的帮助将不胜感激。谢谢！

Answer 1

您在某种程度上过度设计...只需将代码简化为所需的代码，就可以得到想要的...例如：

find_cycle(G,Vs) :-
  member(V-_Edges,G), // don't care about starting point
  find_cycle(G,V,[],Vs).

find_cycle(G,V,SeenVs,[V|SeensVs]) :-
  memberchk(V,SeenVs).
...