prolog语言中的有向图

Question

我定义了边缘，但我应该如何使其具有方向性并获得所有这些问题的答案。

​

​

Answer 1

你可能会发现Eric S.Roberts写的这本书对学习Prolog很有用。这是一本很棒的书，递归是Prolog的核心。但是从图书馆买，或者买二手的，因为它是愚蠢的昂贵的新的。

有向图是一种图，其中的边具有与其关联的方向:如果节点起点连接到节点目的地，则可以从起点到目的地，但不能反向移动。方向性是通过约定隐含的。在赋值的edge/2中，第一个参数假设p(1,2)是起点，第二个参数假设p(2,2)是目的地。所以..。

edge( p(1,2), p(2:2) ).

在p(1,2)和p(2,2)之间存在一条边，以便可以从p(1,2)移动到p(2,2)，但不能沿另一个方向移动。

但这都是惯例。没有任何理由不能使用额外的参数来定义图的边，以指示边的方向性：

• edge(a,b,>).

可能表示您可以从a旅行到b，但反之亦然，while

• edge(a,b,<).

可能表示您可以将从 b旅行到 a ，但反之亦然，则可能表示可以进行双向旅行。

因此，您可以这样定义有问题的图(我使用:/2，因为它更简洁，并且不需要输入)：

edge( 1:1, 2:2 ).
edge( 1:2, 2:2 ).
edge( 2:2, 3:1 ).
edge( 3:1, 2:1 ).
edge( 2:2, 2:3 ).
edge( 2:3, 3:3 ).

遍历图非常简单(特别是如果您不必担心图中的循环)：

connected(A,B) :- % A and B are directly connected
  edge(A,B).      % - If you can get from A to B.
connected(A,B) :- % A and B are indirectly connected
  edge(A,X),      % - If A is directly connected to a node X
  connected(X,B). % - such that X is connected to B

这就是它的全部。

如果你想知道你在图表中走了哪条路(这条路)，这并不复杂-我们只需要跟踪我们从哪里开始，我们去了哪里：

connected(A,B,[A|P]) :-     % a path always starts with the origin
  connected_via(A,B, P ).   % - then invoke the helper predicate

connected_via(A,B,[B]) :-   % A is directly connected to B and the path ends with B
  edge(A,B).                % - if an edge exists between A and B.
connected_via(A,B,[X|P]) :- % A is  indirectly connected to B (and we add X to the path) 
  edge(A,X),                % - if an edge exists between A and some node X
  connected_via(X,B,P).     % - such that X is connected to B.