序言图深度优先搜索

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)

我在 prolog 中不能做的是将 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 中，如果您尝试 "accumulate" 一个列表，如果您需要的元素是通过回溯获得的，则可能具有挑战性。

下面的代码是 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
| ?-

Answer 2

只需将您的代码直接翻译成 Prolog。不要想太多；说出你的意思：

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

dfs(Graph, V, Visited, Return) :-
   visited(V, Visited),
   return(Graph, V, Visited, Return).

dfs(Graph, V, Visited, Return) :-
   \+ visited(V, Visited),
   appended(Visited, [V], Visited2),
   neighbor(Graph, V, N),
   dfs(Graph, N, Visited2).

谓词 visited/2、return/4、appended/3、neighbor/3 应该很容易实现。

正确第一，效率第二。

序言图深度优先搜索

prolog graph depth first search

graph-theory

prolog

depth-first-search