haskell - 您将如何在 Haskell 中表示图(与旅行商问题相关的那种)

Question

在haskell中表示一棵树很容易:

data Tree a = Node Tree a Tree | Leaf a

但那是因为它不需要命令式“指针”的概念，因为每个 Node/Leaf 都有一个，而且只有一个父节点。我想我可以将它表示为 Maybe Int 的列表列表s ...用 Nothing 创建一个表对于那些在 和 Just n 之间没有路径的节点对于那些这样做的人......但这看起来真的很丑陋和笨拙。

Answer 1

您可以使用类似的类型

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

节点列表是该节点的传出(或传入，如果您愿意)边缘。由于您可以构建循环数据结构，因此可以表示任意(多)图。这种图结构的缺点是一旦构建就无法修改。为了进行遍历，每个节点可能需要一个唯一的名称(可以包含在 a 中)，以便您可以跟踪您访问过哪些节点。