prolog - 序言中的 dfs。访问一个节点一次

Question

dfs(S, Visited, Path) :-
    move(S, S2),
    \+member(S2, Visited),
    dfs(S2, [S2|Visited], Path).

你好，

以上一段代码是Prolog中dfs的原型(prototype)。但是，move 基于回溯，因此我丢失了 Visited 列表，因此无法确保我访问了每个节点一次。如何在不使用全局变量和类似的情况下处理它 - 我想使用纯逻辑解决方案。

Answer 1

您可以为 dfs 使用迭代(基于堆栈)方法而不是递归，如 How to implement depth first search for graph with non-recursive aprroach 中所述。 .

Move 将被调用以检查可能的邻居是什么。这里的区别在于您首先遍历可能的候选人。通过始终将它们放在堆栈的前面，我们迭代地首先进入深度，因为堆栈的顶部将首先被探索。

例如，可以使用 findall

查找可能的下一个候选对象

示例:

%% Dfs starting from a root
dfs(Root) :-
    dfs([Root], []).
%% dfs(ToVisit, Visited)
%% Done, all visited
dfs([],_).
%% Skip elements that are already visited
dfs([H|T],Visited) :-
    member(H,Visited),
    dfs(T,Visited).
%% Add all neigbors of the head to the toVisit
dfs([H|T],Visited) :-
    not(member(H,Visited)),
    findall(Nb,move(H,Nb),Nbs),
    append(Nbs,T, ToVisit),
    dfs(ToVisit,[H|Visited]).