在图中循环检测

Question

我们得到一个图表,其中包含以下事实:

edge(a,b)
edge(a,c)
edge(b,a)
edge(c,d)
edge(d,d)
edge(d,e)
edge(e,f)
edge(f,g)
edge(g,e)

我们被要求定义一个规则,cycle(X)确定是否存在从节点开始的循环X.

我真的迷失了如何做到这一点,我试图遍历节点并检查下一个节点是否会再次成为起始节点,但我似乎无法让它工作

Answer 1

Archie 的想法是一个很好的起点，但如果在搜索路径时发现另一个循环，它将创建一个无限循环。

我也已经很多年没有使用 prolog 了，但是您将需要类似的东西path(X,Y,Visited)，您可以在其中跟踪访问的节点，防止无限循环。

Answer 2

自从我使用 Prolog 以来已经有一段时间了，但也许这种方法会起作用：路径是一系列边，其中每个边从前一个边结束的节点开始（例如 a -> b、b -> c、c -> d). 普通路径是一条边，更复杂的路径可以通过采用现有路径并向其添加一条边来形成。循环是在同一节点上开始和结束的路径。您可以使用这些定义来构建您的 Prolog 规则吗？