4

在 haskell 中表示一棵树非常容易：

data Tree a = Node Tree a Tree | Leaf a

但那是因为它不需要命令式“指针”的概念，因为每个节点/叶子都有一个，并且只有一个父级。我想我可以将它表示为 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]}

构建每个边有两个（无法区分的）副本的完整图很容易：

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

但是尝试构建一个每个副本都有一个副本！（想象一下，其中涉及一些昂贵的计算e v1 v2）。

于 2011-07-28T15:19:55.610 回答
2

其他人概述的打结技术可以工作，但有点痛苦，尤其是当您尝试动态构建图形时。我认为您描述的方法更实用一些。我会使用节点类型的数组/向量，其中每个节点类型都包含一个邻居列表/数组/向量（除了您需要的任何其他数据之外），表示为适当大小的整数，其中整数是节点的索引大批。我可能不会使用Maybe Ints. Int您仍然可以使用 -1 或任何合适的值作为未初始化的默认值。一旦您填充了所有邻居列表并知道它们是好的值，您将不需要提供的故障机制Maybe无论如何，正如您所观察到的那样，这会带来开销和不便。但是，如果您需要完全使用节点指针类型可能包含的所有可能值，那么您使用 Maybe 的模式将是正确的做法。

于 2011-07-28T16:38:05.170 回答
2

最简单的方法是给图中的顶点唯一的名称（可以像 Int 一样简单）并使用通常的邻接矩阵或邻居列表方法，即，如果名称是 Int，则使用数组 (Int,Int)布尔型或数组 Int [Int]。

于 2011-07-28T20:51:06.400 回答
1

看看这种打结技术，它用于创建圆形结构。如果您的图表包含循环，您可能需要它。

此外，您可以使用邻接矩阵来表示您的图形。

或者，您可以保留每个节点与入站和出站边缘之间的映射。

事实上，它们中的每一个在一种情况下都是有用的，而在另一种情况下是痛苦的。根据您的问题，您必须进行选择。

于 2011-07-28T15:15:42.160 回答