3

免责声明：作者是 Erlang 的新手。

我想在 Erlang 中实现某种最短路径算法。

Erlang中有图数据结构的标准实现：http ://www.erlang.org/doc/man/digraph.html

但是，我还没有找到有关它使用的实际数据结构的任何信息。

主要是我想知道：

  • 为顶点动作获取所有“邻居”的最坏情况是什么？
  • 从图中获取顶点的最坏情况是什么？
4

1 回答 1

8

一个有向图使用 3 个 ets 表（顶点、边和相邻顶点）。

所以这两个操作都是 O(1)。

看一下 OTP 代码，它很干净，在大多数情况下是惯用的 Erlang。stdlib 的 gen.erl + gen_server.erl、proc_lib.erl 和 sys.erl 是必须阅读的 :)

于 2011-07-15T20:56:51.810 回答