ocaml 中优雅的 BFS

Question

我想修复我的 bfs 函数，它的问题是当它接收到不存在的节点时，它也将它们打印为已访问。

而且这个函数已经很庞大了，所以添加一个检查，比如：

if node not in graph then ... 也会使我的函数更加膨胀，我想避免这种情况，因为我想看到一个更短的函数，即 "eye-debuggable".

此外，我选择 Hashtable 是因为与 Set 相对：

它是可变的
它是一个数组但是Set是一个平衡二叉树

（如果您个人喜欢 Set，请告诉我原因）

    type 'a graph = Gr of ('a * 'a list) list

    let get_neighbors node (Gr g) = 
        try List.assoc node g with Not_found -> []

    let bfs start g = 
        let v = Hashtbl.create 100 in (*ideally it should be the # of distinct nodes*)
        let q = Queue.create () in    (*v is for visited nodes*)

        let rec bfs' cur_n acc = 
                get_neighbors cur_n g |>
                List.iter
                (fun n -> 
                    try Hashtbl.find v n
                    with Not_found -> 
                        Hashtbl.add v n ();
                        Queue.push n q);
                Hashtbl.add v cur_n (); 
                try bfs' (Queue.pop q) (cur_n::acc)
                with Queue.Empty -> List.rev (cur_n::acc) in
                bfs' start []

示例：

    let g =  
        Gr [
             ('a', ['e'; 'b'; 'c']); 
             ('b', ['e'; 'd']); 
             ('e', ['d'; 'f']);
             ('g', ['t';'s'])
           ]

    # bfs 'a' g;;
    - : char list = ['a'; 'e'; 'b'; 'c'; 'd'; 'f']
    # bfs 'z' g;;
    - : char list = ['z'] (*doesn't make sense, g doesn't have 'z' node*)

Answer 1

在我看来，get_neighbors 中的 Not_found 异常表示一个不存在的节点。但是您的代码正在处理这种情况，如果它指示没有后继节点。

如果您的图表结构良好，则邻居列表不应包含任何不存在的节点。所以这个节点唯一可以来自的地方就是初始调用。

所以我会把这个 Not_found 异常的处理移到最外层。

ocaml 中优雅的 BFS

Elegant BFS in ocaml

algorithm

ocaml

graph-theory

breadth-first-search