如何在Haskell中表示图（与旅行商问题相关的那种）？

Question

在Haskell中表示一棵树相当容易：

data Tree a = Node Tree a Tree | Leaf a

但这是因为它不需要命令式样式的“指针”概念，因为每个节点/叶子只有一个父级。我猜可以将其表示为Maybe Int的列表，以创建一个表格，在其中没有路径的节点上使用Nothing，在具有路径的节点上使用Just n...但这似乎非常丑陋和笨重。

- Tom Busby

---

请查看functional graph library，尽管如果我没有记错的话，它正在进行重大改写。 - Antal Spector-Zabusky

请注意，您可以通过依赖于惰性求值轻松构造具有循环的图。例如，我相信let xs = () : xs in xs将构造一个单元素循环列表，而不是无限重复元素的列表。 - C. A. McCann

Answer 1

您可以使用类似于以下的类型：

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

节点列表是该节点的出边（如果您喜欢，也可以是入边）。由于您可以构建循环数据结构，因此这可以表示任意（多）图形。这种图形结构的缺点是一旦构建它，就无法修改它。为了进行遍历，每个节点可能需要一个唯一的名称（可以包含在 a 中），以便您可以跟踪已访问的节点。

- augustss

---

它可以在通常意义下“修改”之后进行修改。我觉得你指的是节点可能会引用原始数据的问题，因此不仅需要替换树的根路径或替换列表的头并共享尾部，还需要替换具有到要替换的节点的路径的任何节点。在一个无向图中，这意味着绝对所有的东西都需要被替换。 - C. A. McCann

由于在Haskell中无法修改任何内容，所以我指的是“显而易见”的事情。 :) 如果您将其表示为从节点名称到节点的映射，您可以通过更改映射来更轻松地“修改”它。 - augustss

好的。：] 我只是想为观众澄清一下，因为人们经常谈论“使用部分共享创建新结构”作为“修改”原始结构，你是否意味着这种“修改”难以或不可能实现，而不是字面上的原地修改不可能（尽管这也是正确的）。Stack Overflow在Google中排名很高，所以我试图考虑到未来可能会遇到这些问题的匿名新手。 - C. A. McCann

Answer 2

免责声明：以下是一个几乎毫无意义的“绑定节点”技术练习。如果您想要实际使用图形，请使用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中涉及到一些昂贵的计算。）

- n. m.

---

请注意--参见augustss的答案和我的评论，了解为什么如果您确实“想要实际使用”此类结构，则绑扎结构并不是很好的选择。另一方面，这样的技术有时可能会很有用，例如使用循环列表来表示在固定内存量中无限重复的序列。 - C. A. McCann

Answer 3

其他人提供的打结技术可能有效，但有点麻烦，特别是当你试图即时构建图表时。我认为你描述的方法更加实用。我会使用节点类型的数组/向量，其中每个节点类型都包含一个邻居列表/数组/向量（除了您需要的任何其他数据），表示为适当大小的整数，其中整数是索引到节点数组中的索引。我可能不会使用Maybe Int。使用Int，您仍然可以使用-1或任何适当的值作为未初始化的默认值。一旦您填充了所有的邻居列表并知道它们是好的值，您将不需要Maybe提供的失败机制，这正如您所观察到的那样，会带来开销和不便。但如果您需要完全利用节点指针类型可能包含的所有可能值，则使用Maybe是正确的做法。

- mightybyte

Answer 4

最简单的方法是给图中的顶点分配唯一的名称（可以是简单的整数），然后使用常规的邻接矩阵或邻接表方法，即如果名称是整数，则使用数组（Int，Int）Bool或数组Int [Int]。

- Omar Antolín-Camarena

Answer 5

看一下这个打结技巧，它用于创建循环结构。如果你的图包含循环，你可能需要它。

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

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

实际上，它们每一个在某种情况下都有用处，在其他情况下则会带来麻烦。根据你的问题，你必须做出选择。

- Mihai Maruseac