优雅的ocaml BFS

Question

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

这个函数已经很大了，所以添加一个检查如下：

if node not in graph then ...也会使我的功能更加膨胀，我想避免这一点，因为我希望看到一个更短的函数，即“眼睛可调试器”。

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

1. 它是可变的
2. 它是一个数组，但是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

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

如果您的图结构良好，则邻居列表不应该包含任何不存在的节点。因此，该节点可以来自的唯一位置是初始调用。

因此，我会将这个Not_found异常的处理移到最外层。