Prolog 图深度优先搜索

Question

我见过有关深度优先搜索的其他问题，但我的问题略有不同，我真的不明白。在序言中，我将无向图表示如下:

[0-[1,5]、1-[0,2]、2-[1,3]、3-[2,0]、5-[0]]

这是一组键值对，其中键代表节点，列表:-[]代表其邻居。

我不知道如何使用这个模型进行深度优先搜索。我尝试了很多解决方案。我想要一个非常基本的递归算法，如下所示:

dfs(v, visited):
  if visited[v] then return
  visited.insert(v)
  foreach neighbor of v:
    dfs(neighbor, visited)

我在序言中不能做的是将访问作为可变引用传递，该引用将由每个邻居递归地为下一个邻居修改。

因为如果我把它翻译成序言:

% here Graph contains the entire key-value pairs list,
% Node-Neighbor is the current node with its neighbors.
dfs(Graph, Node-Neighbors, Visited) :-
    \+ member(Node, Visisted),
    % Now here I could get the next neighbor within neighbor, like so:
    member(Node1,Neighbors),
    % Then gets its own neighbors too by:
    member(Node1-Neighbors1, Graph),
    % but here I'm stuck...

我需要某种折叠，其中每个邻居调用 dfs 并将其结果传递给下一个邻居，但我不知道该怎么做......

谢谢。

Answer 1

传统的DFS算法涉及递归和堆栈，基本上是一种回溯机制。在 Prolog 中，如果您尝试“累积”一个列表，如果您需要的元素是通过回溯获得的，那么这可能会是一个挑战。

以下代码是 DFS 搜索的非常简单的呈现，并将写出 DFS 搜索中的节点:

dfs(Graph, StartNode) :-
    dfs(Graph, StartNode, []).

dfs(Graph, Node, Visited) :-
    \+ member(Node, Visited),
    member(Node-Neighbors, Graph),
    write(Node), nl,
    member(NextNode, Neighbors),
    dfs(Graph, NextNode, [Node|Visited]).

这两个 member 调用看起来有点像您尝试执行的操作，但并不完全相同。它们共同构成了该结构的 DFS 遍历的关键。

查询这个你会得到:

| ?- dfs([0-[1,5], 1-[0,2], 2-[1,3], 3-[2,0], 5-[0]], 0).
0
1
2
3
5

yes
| ?-

但是，写出图中的节点并不是特别有用。我们想将它们收集在一个列表中。可以修改上面的内容，使其成为搜索路径上每个节点都成功的谓词。

dfs(Graph, StartNode, Node) :-
    dfs(Graph, StartNode, [], Node).

dfs(Graph, ThisNode, Visited, Node) :-
    \+  member(ThisNode, Visited),
    (   Node = ThisNode                     % Succeed finding a new node
    ;   member(ThisNode-Neighbors, Graph),  % Or... find the next node
        member(NextNode, Neighbors),
        dfs(Graph, NextNode, [ThisNode|Visited], Node)
    ).

这会导致:

| ?- dfs([0-[1,5], 1-[0,2], 2-[1,3], 3-[2,0], 5-[0]], 0, Node).

Node = 0 ? a

Node = 1

Node = 2

Node = 3

Node = 5

no
| ?-

现在您可以使用 findall/3 获取节点列表:

dfs_path(Graph, StartNode, Nodes) :-
    findall(Node, dfs(Graph, StartNode, Node), Nodes).

现在你可以写:

| ?- dfs_path([0-[1,5], 1-[0,2], 2-[1,3], 3-[2,0], 5-[0]], 0, Nodes).

Nodes = [0,1,2,3,5]

yes
| ?-