在Java或其他命令式编程中，图形可以表示为 matrix 或 adjacent list . adjacent list 可能是最受欢迎的，因为它使用 array 时非常紧凑和方便 .
在函数式编程中，我们通常不使用 mutable array . 那么通常我们如何在OCaml或其他函数式编程中呈现图形？
用 map 替换数组？
在ocaml 99, graph中列出了4种方式：
edge-clause form
一种方法是列出所有边，边是一对节点 . 在这种形式中，相反描绘的图表表示为以下表达式：
['h', 'g'; 'k', 'f'; 'f', 'b'; 'f', 'c'; 'c', 'b']
我们称之为edge-clause形式 . 显然，无法表示孤立的节点 .
graph-term form
另一种方法是将整个图表表示为一个数据对象 . 根据图形的定义，作为一对两组（节点和边），我们可以使用以下OCaml类型：
type 'a graph_term = { nodes : 'a list; edges : ('a * 'a) list }
然后，上面的示例图表由：
let example_graph =
{ nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
edges = ['h', 'g'; 'k', 'f'; 'f', 'b'; 'f', 'c'; 'c', 'b'] }
我们称之为图形术语形式 . 请注意，列表保持排序，它们确实是集合，没有重复的元素 . 每条边在边列表中只出现一次;即，从节点x到另一个节点y的边缘表示为（x，y），该对（y，x）不存在 . 图形术语表格是我们的默认表示 . 您可能希望使用集而不是列表来定义类似的类型 .
adjacency-list form
第三种表示方法是将与该节点相邻的一组节点与每个节点相关联 . 我们称之为邻接表格 .
human-friendly form
到目前为止我们介绍的表示非常适合自动处理，但它们的语法不是非常用户友好 . 手动输入术语既麻烦又容易出错 . 我们可以如下定义更紧凑和“人性化”的符号：图形（带有char标记的节点）由一串原子和X-Y类型的术语表示 . 原子代表孤立的节点，X-Y术语代表边缘 . 如果X显示为边的 endpoints ，则会自动将其定义为节点 . 我们的例子可以写成：
"b-c f-c g-h d f-b k-f h-g"
考虑到处理效率，我认为上述4种方法都不够好 .
对于 record type graph-term form ，没有有效的方法来定位节点（始终为 O(n) ）并找到连接到节点的边 .
3 回答
有两点需要考虑：图表的表示和某些图算法中使用的中间数据结构 .
我认为邻接列表形式是表示图形的最有效的内存方式 . 可以通过树或类型的 Map 来改进一点
但是当你想运行像“强连接组件”或“拓扑排序”这样的算法时，那些算法很可能会使用可变数组来实现它 .
注意，在像Haskell这样的语言中，ST monad使得有可能具有临时可变状态，即数组），而不是全局状态 . 使用它的功能仍然是整体纯粹的 .
您可能对OCamlGraph库（http://ocamlgraph.lri.fr）感兴趣，它提供了各种图形实现，包括持久性或可变性，以及一堆经典算法 .
在命令式语言中，图形表示的选择取决于您尝试解决的问题 .
功能语言也是如此 .
Ocamlgraph提供了足够的抽象，您可以编写独立于底层图表示的算法，当然算法的运行时仍然取决于实现 .