1

我想在 Prolog 中编写这个算法，首先我需要从图表列表中创建一个矩阵。我以前做过（也在你们中的一些人的帮助下，伙计们），但现在我不知道如何将它存储在列表列表中（我认为这是 prolog 情况下的最佳方法）。我想我可以从那里继续（在每个算法中都有三重 for 循环）。程序的逻辑对我来说并不难，而是如何处理数据。很抱歉打扰并提前致谢！

我的矩阵生成器：

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

matrix :- allnodes(X),printmatrix(X).

node(X) :- graph(X,_).
node(X) :- graph(_,X).
allnodes(Nodes) :- setof(X, node(X), Nodes).

printedge(X,Y) :-    graph(Y,X), write('1 ').
printedge(X,Y) :- \+ graph(Y,X), write('0 ').

printmatrix(List):- member(Y, List),nl,member(X, List),printedge(X,Y),fail.
4

1 回答 1

2

您之前的问题Prolog中的邻接矩阵处理了图形邻接矩阵的视觉显示（逐行显示）。在这里，我们讨论如何将邻接矩阵实现/表示为 Prolog 项。特别是，我们将采用上面显示的allnodes/1谓词作为获取所有节点列表的方法。

Prolog 缺少任何本机“矩阵”数据类型，因此这里采用的方法是使用列表列表来表示邻接矩阵。条目由 0 和 1 中的“行”组织，表示对应于行的节点与对应于列的节点的邻接。

查看您的示例图/2事实，我发现您已经包含了一个自边缘（从 a 到 a）。我不确定您是否打算将图设为有向图或无向图，因此我将假设有向图是有意的，并注意如果要使用无向图，则需要进行小的更改。

这里有一个“设计模式”，它通过将规则应用于列表中的每个项目来定义列表。在这里，我们用一种方法来构造“矩阵”的每一行，并且（以此作为我们的规则）来构造整个列表列表。

/* construct adjacency matrix for directed graph (allow self-edges) */
adjacency(AdjM) :-
    allnodes(L),
    adjMatrix(L,L,AdjM).

adjMatrix([ ],_,[ ]).
adjMatrix([H|T],L,[Row|Rows]) :-
    row_AdjM(H,L,Row),
    adjMatrix(T,L,Rows).

row_AdjM(_,[ ],[ ]).
row_AdjM(X,[Y|Ys],[C|Cs]) :-
    (   graph(X,Y)
     -> C = 1
     ;  C = 0
    ),
    row_AdjM(X,Ys,Cs).

如果指的是无向图，则应将调用graph(X,Y)替换为( graph(X,Y); graph(Y,X) )允许在任一方向上考虑边的替代方法。

于 2011-05-06T12:44:42.073 回答