3

私は今graph関連data structureして書き始めます。algorithmsOCaml

私は OCaml で機能的な方法でそれらを書きたいと思っていますarray。

しかし、それらすべてを を使用して記述した場合list、それは効率的または意味のあるものになるでしょうか?

4

2 に答える 2

4

これはすべて、実装するアルゴリズムの種類と、疎なグラフと密なグラフのどちらを検討するかによって異なります。通常、密なグラフは行列で表されます (ちなみに、行列は不変に保たれ、機能的に使用できます)。

O(1) 更新を伴う配列が必要な場合 (ノードのマーキングなど)、配列を更新可能な構造体として提示するラッパー ライブラリを使用して機能的な方法で配列を使用し、毎回新しい配列を提供することができます。秘訣は、変更可能な配列を「ヘッド」バージョンとして保持し、過去のバージョンを「ヘッド」からのデルタとして保持することにより、これらの更新を実装することです。これにより、すべての必須の問題がモジュール内にまとめられ、意味的には少なくとも機能的なインターフェイスが提供されます。

まばらなグラフがある場合、「隣接リスト」について話すのが一般的です。O(n) のアクセス権があるため、グラフが非常にまばらな場合 (絶対的に次数が小さいノード) でない限り、それらを使用するのは悪い考えだと思います。O(log n) でテストできるので、二分木風のSetほうがはるかに適していると思います。

于 2013-03-29T06:14:14.117 に答える
4

すべてにリストを使用する必要はありません。ライブラリには他にも多くの不変データ構造があり、独自に定義することもできます。グラフは、ノードからサクセサーのリストへのマップと考えることができます。私はこの表現を使って OCaml で大量のグラフ処理コードを書きましたが、その結果にはいつも満足しています。

アップデート

これが私が話している表現のスケッチです。ノードに一意の文字列でラベルを付けることを前提としています。（monniauxがコメントしたように）後継者のリストを使用することは、密なグラフよりも疎なグラフにおそらく適していることに注意してください。

type label = string
module GMap = Map.Make(struct type t = label let compare = compare end)
type 'a node = label * 'a * label list
type 'a graph = 'a node GMap.t

let empty = GMap.empty

let add (label: label) (contents: 'a) successors (graph: 'a graph) : 'a graph =
    GMap.add label (label, contents, successors) graph

長さ 2 のサイクルだけを含むグラフを作成します。

# let g = add "a" () ["b"] (add "b" () ["a"] empty);;
val g : unit graph = <abstr>
于 2013-03-28T23:35:04.997 に答える