Prolog中定义图:边和路径，查找两个顶点之间是否有路径 [英] Define graph in Prolog: edge and path, finding if there is a path between two vertices

问题描述

我对 Prolog 很陌生.我在 graph.pl 中定义了下图:

I'm very new to Prolog. I defined in graph.pl the following graph:

这是我的 Prolog 代码:

And here's my Prolog code:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

我是这样理解的:只有在顶点X之间有边时，顶点X和顶点Y之间才有路径code> 和顶点 Z 并且在顶点 Z 和顶点 Y 之间有一条路径(某种递归).

I understand it like this: there is a path between vertex X and vertex Y only if there is an edge between vertex X and vertex Z AND there is a path between vertex Z and vertex Y (some kind of recursion).

对于所呈现的图表是否正确?当我向 Prolog 询问顶点 A 和顶点 F 之间的路径时，它给了我 true ...这甚至是不对的！这段代码可能有什么问题?

Is that right for the presented graph? When I ask Prolog about the path between vertex A and vertex F it gives me true ... which isn't even right! What might be wrong in this code?

推荐答案

图中的循环.您需要跟踪您正在访问的节点，并检查它们.试试这个，使用带有累加器的辅助谓词来跟踪访问的节点:

Cycles in the graph. You need to track what nodes you're visiting, and check them. Try this, using a helper predicate with an accumulator to track the visited nodes:

path(A,B) :-   % two nodes are connected, if
  walk(A,B,[]) % - if we can walk from one to the other,
  .            % first seeding the visited list with the empty list

walk(A,B,V) :-       % we can walk from A to B...
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - we haven't yet visited X, and
  (                  % - either
    B = X            %   - X is the desired destination
  ;                  %   OR
    walk(X,B,[A|V])  %   - we can get to it from X
  )                  %
  .                  % Easy!

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

这篇关于Prolog中定义图:边和路径，查找两个顶点之间是否有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！