prolog实现深度优先搜索

在Prolog中，深度优先搜索（Depth-First Search, DFS）通常通过递归实现。DFS是一种用于遍历或搜索树和图的算法，它首先尽可能深地探索一条路径，直到到达叶子节点，然后回溯到上一个节点并尝试其他分支。

下面是一个简单的Prolog程序，展示了如何使用递归规则来实现深度优先搜索：

% 定义图节点和边的关系
graph(nodeA, nodeB).
graph(nodeB, nodeC).
graph(nodeC, nodeD).
graph(nodeD, nodeE).

% 深度优先搜索函数
dfs(Node, Visited, [Node|Visited]):-
    % 如果节点未访问过，则标记为已访问并继续遍历其邻居
    not(member(Node, Visited), mark_visited(Node)),
    % 对每个相邻节点递归调用dfs
    findall(Neighbor, graph(Node, Neighbor), Neighbors),
    dfs(Neighbor, Visited, [Node|Neighbors]).

mark_visited(Node):-
    % 添加到已访问列表
    setarg(1, Visited, [Node|_]).
dfs(Node, _, []):-  % 当所有路径都探索完，返回空列表表示结束

% 测试
dfs_start(NodeA, VisitedNodes) :-
    dfs(NodeA, [], VisitedNodes).

在这个例子中，`dfs_start/2`宏启动了从`nodeA`开始的深度优先搜索，并返回访问过的节点列表。当你运行这个查询时，会得到类似的结果：

?- dfs_start(nodeA, Visited).
VisitedNodes = [nodeA, nodeB, nodeC, nodeD, nodeE].