基于Prolog实现带代价的DFS与BFS，计算节点0到4的总路径代价

图结构定义 #

根据拓扑图定义边的事实，每条边包含起点、终点和通行代价：

% edge(起点, 终点, 通行代价)
edge(0, 1, 1).
edge(0, 2, 2).
edge(1, 3, 3).
edge(2, 3, 1).
edge(2, 4, 5).
edge(3, 4, 1).

带代价的深度优先搜索（DFS） #

DFS通过递归深入路径，记录已访问节点避免循环，同时累加路径代价：

% 核心递归：dfs(当前节点, 目标节点, 已访问列表, 当前总代价, 反转路径, 总代价)
dfs(Node, Node, Visited, Cost, [Node|Visited], Cost).

dfs(Current, Goal, Visited, CurrentCost, Path, TotalCost) :-
    edge(Current, Next, EdgeCost),
    \+ member(Next, Visited), % 跳过已访问节点
    NewCost is CurrentCost + EdgeCost,
    dfs(Next, Goal, [Current|Visited], NewCost, Path, TotalCost).

% 对外调用接口：返回从0到4的路径及总代价
dfs_path(Path, TotalCost) :-
    dfs(0, 4, [], 0, ReversePath, TotalCost),
    reverse(ReversePath, Path). % 反转得到从起点到目标的顺序路径

DFS查询示例 #

?- dfs_path(Path, Cost).
Path = [0, 1, 3, 4], Cost = 5 ;
Path = [0, 2, 3, 4], Cost = 4 ;
Path = [0, 2, 4], Cost = 7.

DFS优先遍历深度方向的路径，按边定义的顺序返回所有可行路径及其代价。

带代价的广度优先搜索（BFS） #

BFS使用队列实现层序遍历，队列元素保存当前节点、已访问列表和累计代价：

% 核心递归：bfs(队列, 目标节点, 反转路径, 总代价)
bfs([(Node, Visited, Cost)|_], Node, [Node|Visited], Cost).

bfs([(Current, Visited, CurrentCost)|Rest], Goal, Path, TotalCost) :-
    % 生成当前节点的所有未访问邻接节点及新代价
    findall(
        (Next, [Current|Visited], NewCost),
        (edge(Current, Next, EdgeCost), \+ member(Next, Visited), NewCost is CurrentCost + EdgeCost),
        NewNodes
    ),
    append(Rest, NewNodes, NewQueue), % 新节点加入队列尾部（先进先出）
    bfs(NewQueue, Goal, Path, TotalCost).

% 对外调用接口：初始化队列，返回从0到4的路径及总代价
bfs_path(Path, TotalCost) :-
    bfs([(0, [], 0)], 4, ReversePath, TotalCost),
    reverse(ReversePath, Path).

BFS查询示例 #

?- bfs_path(Path, Cost).
Path = [0, 2, 4], Cost = 7 ;
Path = [0, 2, 3, 4], Cost = 4 ;
Path = [0, 1, 3, 4], Cost = 5.

BFS按节点层数顺序遍历，优先返回节点数最少的路径，再返回其他路径。

内容的提问来源于stack exchange，提问作者Samridh Girdhar