Ocaml：即使已经找到，也会重复图形中的路径

Question

我编写了一些函数来搜索从起始节点到终止节点的可能路径列表。函数list_of_paths正确返回从起点到终点的所有可能路径，但是即使已找到列表，也重复列表内的相同路径。

例如，调用函数：list_of_paths 2 7 (List.rev (bfs g1 2)) (node_succ g1) 2

返回：[[2; 3; 6; 7]; [2; 3; 6; 7]; [2; 3; 4; 6; 7]; [2; 3; 6; 7]; [2; 1; 5; 6; 7]; [2; 3; 6; 7]; [2; 1; 5; 6; 7]]

您可以看到重复了相同的路径。有人可以告诉我错误在哪里吗？这是我写的代码：

type weight = int;;
type 'a graph = Gr of (int * weight * int) list;;
let g1 =  Gr [(1,3,2);(1,9,5);(2,2,3);(5,4,6);(3,1,6);(3,7,4);(6,2,7);(4,4,6)];;

let rec node_succ (Gr graph) node =
    let rec f_aux = function
        [] -> []
        | (x,y,z)::tail -> 
            if x = node then z::f_aux tail
            else if z = node then x::f_aux tail
            else f_aux tail in f_aux graph;;

let bfs graph s =
    let rec search visited_nodes = function 
        [] -> visited_nodes 
        | head::tail -> 
        if List.mem head visited_nodes then search visited_nodes tail
        else search (head::visited_nodes) (tail @ (node_succ graph head)) in search [] [s];;


let find_paths_bfs start stop graph =
    let extends paths = 
        List.map (function x -> x::paths) (List.filter (function x -> not (List.mem x paths)) (graph (List.hd paths)))
                in let rec s_aux stop = function
                    [] -> raise Not_found
                    | paths::tail -> 
                        if stop = List.hd paths then List.rev paths
                        else s_aux stop (tail @ (extends paths)) in s_aux stop [[start]];; 

let rec list_of_paths start stop reachable_nodes fun_graph_succ s =
    if reachable_nodes = [] then []
    else ((find_paths_bfs s start fun_graph_succ)@(List.tl(find_paths_bfs start stop fun_graph_succ)))
        ::(list_of_paths (List.hd reachable_nodes) stop (List.tl reachable_nodes) fun_graph_succ s);;

函数node_succ返回节点的所有可能的后继者。

函数bfs从起始节点返回所有可达节点。

[C0函数]查找从一个节点开始到另一个节点的一条路径。

Answer 1

您的实现有点难（至少对于像我这样的OCaml新手而言：)。我建议先简化一下。正如我说的那样，我绝对是OCaml的初学者，因此请带一点盐（我敢肯定我的解决方案远非最佳或惯用语言），但我会选择类似的东西：