4

Haskell でツリーを表現するのは非常に簡単です。

data Tree a = Node Tree a Tree | Leaf a

ただし、これは、各ノード/リーフに親が 1 つしかないため、命令型スタイルの「ポインター」の概念が必要ないためです。私はそれを s のリストのリストとして表すことができると思います...間にパスのないノードとパスを持つノードMaybe Intのテーブルを作成します...しかし、それは本当に醜くて扱いにくいようです。NothingJust n

4

5 に答える 5

8

次のようなタイプを使用できます

type Graph a = [Node a]
data Node a = Node a [Node a]

ノードのリストは、そのノードの発信エッジ (または必要に応じて着信エッジ) です。循環データ構造を構築できるため、これは任意の (マルチ) グラフを表すことができます。この種のグラフ構造の欠点は、一度作成すると変更できないことです。トラバーサルを行うには、おそらく各ノードに一意の名前が必要です ( に含めることがaできます)。これにより、どのノードにアクセスしたかを追跡できます。

于 2011-07-28T15:00:13.187 に答える
6

免責事項：以下は、「結び目を結ぶ」テクニックのほとんど無意味な演習です。グラフを実際に使用したい場合は、Fgl が最適です。ただし、循環データ構造を機能的に表現する方法を知りたい場合は、読み進めてください。

Haskell でグラフを表現するのはとても簡単です!

-- a directed graph

data Vertex a b = Vertex { vdata :: a, edges :: [Edge a b] }
data Edge   a b = Edge   { edata :: b, src :: Vertex a b, dst :: Vertex a b }

-- My graph, with vertices labeled with strings, and edges unlabeled

type Myvertex = Vertex String ()
type Myedge   = Edge   String ()

-- A couple of helpers for brevity

e :: Myvertex -> Myvertex -> Myedge
e = Edge ()

v :: String -> [Myedge] -> Myvertex
v = Vertex

-- This is a full 5-graph

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = let vk = v s (zipWith e (repeat vk) mygraph5) in vk

これは、循環的で、有限で、再帰的で、純粋に機能的なデータ構造です。非常に効率的でも美しいものでもありませんが、ほら、ポインタはありません! ここに演習があります: 頂点に入ってくるエッジを含めます

data Vertex a b = Vertex {vdata::a, outedges::[Edge a b], inedges::[Edge a b]}

各エッジの 2 つの (見分けがつかない) コピーを持つ完全なグラフを作成するのは簡単です。

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = 
       let vks = repeat vk
           vk = v s (zipWith e vks mygraph5) 
                    (zipWith e mygraph5 vks)
       in vk

ただし、それぞれのコピーが 1 つあるものを作成してみてください。( に高価な計算が含まれていると想像してくださいe v1 v2)。

于 2011-07-28T15:19:55.610 に答える
2

他の人が概説した結び目を結ぶテクニックは機能しますが、特にその場でグラフを作成しようとしている場合は、少し面倒です。あなたが説明するアプローチはもう少し実用的だと思います。ノード タイプの配列/ベクトルを使用します。各ノード タイプは、(必要な他のデータに加えて) 近隣のリスト/配列/ベクトルを保持し、適切なサイズの int として表されます。int はノードへのインデックスです。配列。私はおそらくMaybe Intsを使用しないでしょう。Int-1 または任意の適切な値を初期化されていないデフォルトとして引き続き使用できます。すべての近隣リストにデータを入力し、それらが適切な値であることを確認したら、によって提供される障害機構は必要ありません。Maybeとにかく、あなたが観察したように、これはオーバーヘッドと不便を課します。ただし、ノード ポインター型に含まれる可能性のあるすべての値を完全に使用する必要がある場合は、Maybe を使用するパターンが適切です。

于 2011-07-28T16:38:05.170 に答える
2

最も簡単な方法は、グラフ内の頂点に一意の名前 (Int のように単純なものでもかまいません) を付け、通常の隣接行列または近傍リスト アプローチのいずれかを使用することです。つまり、名前が Int の場合は、配列 (Int,Int) を使用します。 Bool、または配列 Int [Int]。

于 2011-07-28T20:51:06.400 に答える
1

この結び方のテクニックをご覧ください。円形の構造を作成するために使用されます。グラフにサイクルが含まれている場合に必要になることがあります。

また、隣接行列を使用してグラフを表すこともできます。

または、各ノードとインバウンドおよびアウトバウンド エッジの間のマップを保持できます。

実際、それらのそれぞれは、ある状況では役に立ちますが、別の状況では苦痛になります。問題に応じて、選択する必要があります。

于 2011-07-28T15:15:42.160 に答える