OCAML Depth-First Search

Question

私はOCamlでチュートリアルを行っています（なぜ、私は言語の知識を広げることにしたのですか？）グラフで作業する。このチュートリアルでは、細かく実装できるグラフの幅優先探索を行う方法を教えてくれました。しかし、私は、深さ優先検索のアルゴリズムに苦労しています。これは、チュートリアルが行くところの1つです。「これを深さ優先の方法で試してみることをお勧めしますが、それをやってください。

私はそのように実装しようとしています：let rec dfs graph start end。つまり、私はエッジ（）、開始ノード（start）、終了ノード（end）のリストを取るところでそれをやろうとしています。

私はエッジのリストを使用して、私のグラフを作成しました...しかし

let edges = [ 
    ("a", "b"); ("a", "c"); 
    ("a", "d"); ("b", "e"); 
    ("c", "f"); ("d", "e"); 
    ("e", "f"); ("e", "g") 
];; 

は、私は完全にここから行く場所について迷ってしまいました。どのように私を得るために任意のアドバイスですか？ありがとう。

Answer 1

私はそれをしましたが、検索する必要がある場合は、グラフをリストとして表現するのが奇妙です。地図がはるかに良いでしょう。とにかく、ここではそれが行うの方法は次のとおりです。

let edges = [ 
    ("a", "b"); ("a", "c"); 
    ("a", "d"); ("b", "e"); 
    ("c", "f"); ("d", "e"); 
    ("e", "f"); ("e", "g") 
];; 

let successors n e = 
    List.map (fun (_, v) -> v) (List.filter (fun (u, _) -> n = u) e) 

let dfs graph start f = 
    let rec rdfs visited node = 
    if not (List.mem node visited) then 
     begin 
     f node; 
     let s = successors node graph in 
     List.fold_left rdfs (node::visited) s 
     end 
    else visited 
    in rdfs [] start 

let() = let _ = dfs edges "a" print_string in() 

最初のものは、あなたのノードのすべての直接の後継者を与えるsuccessors関数を定義（List.filter部分がList.map部分は二つの部分が得られたエッジを分割し、あなたのエッジを取得します2番目のものだけを残しておきます（最初のものは当然、後継者を検索するノードです）。

dfs関数は、2つのことを行う内部関数を定義し、作業中のノードが既に訪問されているかどうかを確認しますそうでない場合。

• もしそうであれば、何も変わりません。私たちは訪問先ノードの同じリストを返します。
• 我々が訪問したノードにこのノードを追加し

• ノーであれば、私たちは現在のノードにdfsに与えた関数を適用

  • 、我々は彼の後継者を取る
  • 、

  • それぞれに機能を適用します（ここでは小さなテクニックがあります）。

    List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

    と

    rdfs : string list -> string -> string list

    代わりの

    List.fold_left (fun visited node -> rdfs visited node) ...

    を書いて、私たちは

    List.fold_left rdfs ...

    を書くことができます（ラムダ計算といくつかのと呼ばれるこの奇妙なこととは何か

    λ x · ux η u (x ∉ fv(u))あなたがfun x -> f xを書く場合には、OCamlの中で、あなたが代わりに書き込みfを持っていることができれば、それが何を意味するのか:-P）（（fv(u)をuの自由変数である）、それは次のとおりです。と述べているルールと呼ばれるイータ変換厳密に同等。）

  我々は、すべての訪問のノードが追加された訪問したノードのリストを返す

H私は助けた。