0

我in-place graph BFS在 OCaml 中实现。

这是我的代码：

type graph = {s : int list array;num_v:int;mutable num_e : int};;

let bfs u g p =
  let marker = Array.make g.num_v false
  in
  let q = Queue.create()
  in 
  Queue.push u q;
  let rec add_to_queue v = function
    | [] -> ()
    | hd::tl -> 
      if not marker.(hd) then begin
        marker.(hd) <- true;
        Queue.push hd q;
        p.(hd) <- v
      end; 
      add_to_queue v tl
  in 
  **let rec bfs_go =**
    if Queue.length q > 0 then begin
      let v = Queue.pop q
      in 
      print_int v;
      add_to_queue v g.s.(v);
      bfs_go
    end 
  in 
  bfs_go;;

我认为代码很好，但编译器给了我这个错误：

File "", line 20, characters 4-177: Error: This kind of expression is not allowed as right-hand side of 'let rec'

看来我的实现bfs_go有问题（我用** **标记），但为什么呢？我看不到任何错误。

编辑：

DFS功能风格

let dfs_better u g p =
  let marker = Array.make g.num_v false in
  let rec dfs_go current next =
    match current, next with
      | [], _ -> ()
      | parent::[], [] -> ()
      | parent::next_parent::rest, [] -> dfs_go (next_parent::rest) g.s.(next_parent)
      | parent::rest, node::tl -> 
          if not marker.(node) then begin
            print_int node;
            marker.(node) <- true;
            p.(node) <- parent;
            dfs_go next g.s.(node)
          end;
          dfs_go current tl in 
  marker.(u) <- true;
  dfs_go [u] g.s.(u);;
4

1 回答 1

6

你大概是说

let rec bfs_go () =
  ...;
  bfs_go ()

代替

let rec bfs_go =
   ...;
   bfs_go

编辑：我无法抗拒一些改进。

用你的命令式风格：

let bfs start graph from =
  let marker = Array.make graph.num_v false in
  let q = Queue.create() in 
  let add_to_queue parent node =
    if not marker.(node) then begin
      marker.(node) <- true;
      Queue.push node q;
      from.(node) <- parent;
    end in
  Queue.push start q;
  while not (Queue.is_empty q) do
    let node = Queue.pop q in 
    print_int node;
    List.iter (add_to_queue node) graph.s.(node)
  done

如果你想要更实用的东西：

let bfs start graph from =
  let marker = Array.make graph.num_v false in
  let rec bfs current next = match current, next with
    | [], [] -> ()
    | [], (_::_ as next) -> bfs next []
    | node::current, next ->
      let add parent node next =
        if marker.(node) then next
        else begin
          marker.(node) <- true;
          from.(node) <- parent;
          node :: next
        end in
      print_int node;
      bfs current (List.fold_right (add node) graph.s.(node) next)
  in bfs [start] []

编辑2：

尝试 DFS 问题，完全未经测试（刚刚编译）：

使用数据结构来处理要访问的节点：

let dfs u g p =
  let marker = Array.make g.num_v false in
  let rec dfs_go = function
    | [] -> ()
    | node::next ->
        print_int node;
        let children =
          List.filter (fun child -> not marker.(child)) g.s.(node) in
        List.iter (fun child -> marker.(child) <- true) children;
        dfs_go (children @ next)
  in 
  marker.(u) <- true;
  dfs_go [u];;

仅使用（非尾）递归：

let dfs u g p =
  let marker = Array.make g.num_v false in
  let rec dfs_go node =
    print_int node;
    let go_child child =
      if not marker.(child) then begin
        marker.(child) <- true;
        dfs_go child;
      end in
    List.iter go_child g.s.(node)
  in 
  marker.(u) <- true;
  dfs_go u;;
于 2013-04-02T16:44:34.413 回答