0

私はin-place graph BFSOCamlで実装しています。

ここに私のコードがあります:

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 に答える