Prolog，确定图是否为非循环

本文介绍了Prolog，确定图是否为非循环的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要定义一个谓词acyclic/1，该谓词将一个图作为输入并确定该图是否是非循环的.因此，根据我的理解

I need to define a predicate acyclic/1 that takes a graph in as input and determine if that graph is acyclic. So from my understanding

graph1(a,b). graph1(b,c). graph1(c,a).

将返回否，并且

graph2(a,b). graph2(b,c).

将返回是

我做了一个谓词，以确定图中是否有2个节点连接在一起，如果连接，它们将返回是.

I made a predicate to determine if 2 nodes in a graph are connected and if so they will return yes.

isConnected(X,Y) :- a(X,Z), isConnected(Z,Y).

有没有一种方法可以用来确定图是否是非循环的?

is there a way that I can use this to determine if a graph is acyclic?

我不想使用任何预定义的谓词.

I do not want to use any predefined predicates.

推荐答案

使用 closure0/3 :

:- meta_predicate acyclic(2). :- meta_predicate cyclic(2). acyclic(R_2) :- \+cyclic(R_2). cyclic(R_2) :- closure0(R_2, X0,X), call(R_2, X,X0). ?- acyclic(graph2). true. ?- acyclic(graph1). false.

如果存在以下情况，则

cyclic/1成功:

cyclic/1 succeeds if the following exists:

从X0到X的无环连接，因此:

an acyclic connexion from X0 to X, thus:

closure0(R_2, X0,X)或更详细:

call(R_2, X0,X1), call(R_2, X1,X2), call(R_2, X2,X3), ..., call(R_2, Xn,X) 与X0,X1,...,Xn都成对出现

一个边缘向后

call(R_2, X,X0).

所以这是一个循环.换句话说，循环图是包含至少一个循环的图.该循环由一个非循环部分和一个边缘向后组成.只是这条边缘向后才使它成为一个循环.

so that is a cycle. In other words, a cyclic graph is a graph that contains at least one cycle. And that cycle consists of an acyclic part plus one edge back. And it is only this edge back that makes this a cycle.