图中的循环检测 [英] Cycle detection in a graph

问题描述

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

We are given a graph with the following facts:

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 开始的循环.

And we are asked to define a rule, cycle(X), that determines if there is a cycle starting from the node X.

我真的不知道如何做到这一点，我尝试遍历节点并检查下一个节点是否会再次成为起始节点，但我似乎无法让它工作

I am really lost on how to do this, I tried attempting to traverse the nodes and checking if the next one would be the starting one again but I cannot seem to get it to work

推荐答案

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

Archie's idea is a good starting point, but it will create an infinite loop if it finds another cycle while searching for the path.

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

I also haven't used prolog for years, but you will need something like path(X,Y,Visited), where you keep track of the visited nodes, preventing the endless loops.

这篇关于图中的循环检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！