Prolog有向图实现：已定义边如何设置方向性并求解全部问题

第一步：确认有向边定义 #

你已完成边定义的前提下，只要满足以下要求就完成了有向图的配置：

• 你的edge(Source, Target)事实严格遵循第一个参数为有向边起点，第二个参数为有向边终点的规则
• 删除所有类似edge(X, Y) :- edge(Y, X)的无向图双向映射规则，不需要额外新增其他配置，有向图定义就完成了。

本次作业要求参考：

第二步：实现各作业要求的谓词 #

1. 查询两点直接连接关系 #

直接调用你定义的edge/2谓词即可：

• 查询从A出发的所有出边：edge(A, Target).
• 查询指向B的所有入边：edge(Source, B).
• 查询A到B是否有直接有向边：edge(A, B).

2. 查询两点间的所有简单路径（无环路） #

添加如下路径查询谓词：

% 内部递归谓词：参数依次为起点、终点、已访问节点列表、最终路径
path(X, X, _, [X]).
path(X, Y, Visited, [X|Path]) :-
    edge(X, Next),
    \+ member(Next, Visited), % 避免走环路
    path(Next, Y, [Next|Visited], Path).

% 对外调用接口，自动初始化已访问列表
find_path(X, Y, Path) :-
    path(X, Y, [X], Path).

调用示例：查询a到d的所有路径，输入find_path(a, d, Path).即可输出所有符合要求的路径。

3. 查询两点可达性 #

基于路径谓词直接封装可达性判断：

reachable(X, Y) :-
    find_path(X, Y, _). % 只要存在任意一条路径即判定为可达

调用示例：判断a是否可以到达d，输入reachable(a, d).即可返回true/false结果。

4. 查询两点间的最短路径 #

添加如下最短路径计算谓词：

% 计算路径对应的长度（边的数量）
path_length(X, Y, Path, Length) :-
    find_path(X, Y, Path),
    length(Path, NodeCount),
    Length is NodeCount - 1.

% 提取最短路径和对应长度
shortest_path(X, Y, ShortestPath, MinLength) :-
    % 按长度升序排序所有路径，取第一个即为最短
    setof(Len-Path, path_length(X, Y, Path, Len), [MinLength-ShortestPath|_]).

调用示例：查询a到d的最短路径和对应长度，输入shortest_path(a, d, Path, Length).即可得到结果。

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