我是 Haskell 的新手，我正在嘗試提出一種合適的方式來表示圖表。首先是無向簡單圖的一些背景知識。對于所有頂點 u 和 v，u 和 v 之間的一條邊與 v 和 u 之間的一條邊相同，u 和 v 之間最多有一條邊，u 和 u 之間沒有邊。
稍后我希望能夠撰寫函式來檢查圖形是否為 1）空，2）添加新頂點，3）添加新邊，4）獲取頂點的所有鄰居和 5）獲取所有頂點的串列圖表。
在做研究之后，我對定義圖形資料型別的所有方法有點困惑，我也希望得到一些幫助來澄清。所有人似乎都同意，您需要某種方式來表示頂點/節點以及與其他頂點/節點的邊/鏈接。但是，實作方式不同。
在我完成具有無限數量分支的樹之前，遵循這個問題
我首先想到的是使用帶有型別變數的遞回資料結構定義資料型別，其中每個頂點/節點都有一個包含其關聯節點的串列：
data Node a = Node a [a]
deriving Show
data Graph a = Graph [Node a]
deriving Show
但是，我有點不確定的是，這種表示是否可以在以后插入新的邊。有了這個定義，圖只是一個節點串列，而節點串列又包含它們鏈接/邊緣的節點串列。
在研究了如何在 Haskell 中表示圖形之后，我發現了一些有趣的想法。第一個是只使用型別同義詞來定義一個圖：
type Node = Int
type Element = String
type Edge = (Node, Node)
type Node = (Node, Element)
type Graph = ([Node], [Edge])
在這里，我們知道 Graph 是一個節點串列，其中包含其連接/鏈接/邊的關聯串列。但是，我不確定相應的資料型別定義是什么樣的，并且使用型別變數/引數而不是具體型別。在這方面，我發現這個問題declare-data-constructor-for-graphs建議表示這樣的圖：
type Vertex = Integer
data Graph = Graph [Vertex] [(Vertex, Vertex)]
我猜想使用型別引數可以轉換為：
data Graph a = Graph [a] [(a, a)]
這個對嗎？這個解決方案是否適用于在 Haskell 中創建一個沒有多個邊或回圈的簡單、無向圖？這也支持上面指定函式的創建。
繼續，類似于這個表示，我發現這個問題有向無環圖，其中一個圖被定義為：
data Graph a = Graph [(a,[a])] -- Graph is a list of origins paired with edgeends
在這里，我猜作者將圖定義為一個元組串列，其中每個元組由一個節點及其鏈接節點的串列組成。
我發現的另一種方法是在問題graph-data-type-representation中使用記錄語法。
data Node a = Node { value :: a
, neighbors :: [Node a]
} deriving (Show)
-- or simply,
data Node a = Node a [Node a]
deriving (Show)
我猜這也是同樣的道理。一個節點/頂點有一個值，它的鄰居只是一個其他頂點的串列。在此基礎上，圖形定義將是：
data Graph a = Graph [Node a]
還是我錯了？如果是這樣，這個實作和我最初的想法類似，但在資料節點定義上有所不同。不知道這里更正確。
總而言之，我已經找到了許多在 Haskell 中表示圖形資料型別的方法。但是我對哪種方式最適合我的用例感到有點困惑，即創建一個沒有多個邊或回圈的簡單無向圖，它也支持我想要實作的功能。
期待答案和評論來澄清這一點！
uj5u.com熱心網友回復：
最終使用
data Graph a = Graph [(a, [a])] deriving (Show)
由于代數資料型別只是表示資料的一種方式，因此主要是關于選擇適合您需求的設計。這是閱讀更多資訊的好來源：Learn you a haskell
例如，選擇這種資料型別表示可以通過這種方式將頂點添加到圖形中。
addVertex :: Eq a => Graph a -> a -> Graph a
addVertex (Graph vList) v
| not (containsVertex v vList) = Graph (vList makeVertex v)
| otherwise = Graph vList
makeVertex :: a -> [(a, [a])]
makeVertex x = [(x, [])]
containsVertex :: Eq a => a -> [(a, [a])] -> Bool
containsVertex _ [] = False
containsVertex x ((v, _) : ys) = x == v || containsVertex x ys
因此，以這種方式表達的圖形很容易處理和管理。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/517153.html
標籤：哈斯克尔图形