Jac*_*ale 9 ocaml functional-programming
在Java或其他命令式编程中,图形可以表示为matrix或adjacent list.在adjacent list可能是最流行的,因为它是紧凑,因为它是用方便array.
在函数式编程中,我们通常不使用mutable array.那么通常我们如何在OCaml或其他函数式编程中呈现图形？
用map？替换数组？
在ocaml 99中,图表列出了4种方式:
边缘条款形式
一种方法是列出所有边,边是一对节点.在这种形式中,相反描绘的图表表示为以下表达式:
['h', 'g'; 'k', 'f'; 'f', 'b'; 'f', 'c'; 'c', 'b']
我们称之为edge-clause形式.显然,无法表示孤立的节点.
图形术语
另一种方法是将整个图表表示为一个数据对象.根据图形的定义,作为一对两组(节点和边),我们可以使用以下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)不存在.图形术语表格是我们的默认表示.您可能希望使用集而不是列表来定义类似的类型.
邻接表格
第三种表示方法是将与该节点相邻的一组节点与每个节点相关联.我们称之为邻接表格.
人性化的形式
到目前为止我们介绍的表示非常适合自动处理,但它们的语法不是非常用户友好.手动输入术语既麻烦又容易出错.我们可以如下定义更紧凑和"人性化"的符号:图形(带有char标记的节点)由一串原子和XY类型的术语表示.原子代表孤立的节点,XY术语代表边缘.如果X显示为边的端点,则会自动将其定义为节点.我们的例子可以写成:
"b-c f-c g-h d f-b k-f h-g"
考虑到处理效率,我认为上述4种方法都不够好.
对于record type graph-term form,没有有效的方法来定位节点(O(n)总是)并找到连接到节点的边缘.
有两件事需要考虑：图的表示以及某些图算法中使用的中间数据结构。
我认为邻接列表形式是表示图的最有效的内存方式。可以通过拥有这种类型的树或地图来改进一点
type Graph a = Map a [a]
但是，当您想要运行某些算法（例如“强连通分量”或“拓扑排序”）时，那么这些算法很可能会使用可变数组来实现它。
请注意，在像 Haskell 这样的语言中，ST monad 可以拥有临时可变状态（即数组），而不是全局状态。使用它的函数总体上仍然是纯粹的。