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 に答える