エッジリスト

エッジリストは、グラフをそのエッジのリストとして表すために使用されるデータ構造です。（重み付けされていない）エッジは開始頂点と終了頂点によって定義されるため、各エッジは2つの数値で表すことができます。^[1]エッジリスト全体は、2列の行列として表すことができます。^[2]^[3]エッジリストは、リストの長さの配列として表される隣接リストのバリエーションと考えることができます。^[4]各エッジには2つまたは3つの数値のみが含まれるため、エッジリストの合計スペースはです。^[3] $|V|$ $\Theta (|E|)$

参考文献

^ Munagala, Kameshwar; Ranade, Abhiram (1999)。「グラフアルゴリズムの I/O 複雑性」。第 10 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録。SODA '99。米国ペンシルバニア州フィラデルフィア: Society for Industrial and Applied Mathematics: 687–694。ISBN 9780898714340。
^ 「igraph R マニュアルページ」。igraph.org 。 2019年10月16日閲覧。
^ ab 「グラフの表現」。カーンアカデミー。 2019年10月16日閲覧。
^ Kolaczyk, Eric D. (2009-04-20).ネットワークデータの統計分析：方法とモデル. ニューヨーク. pp. 22. ISBN 9780387881461. OCLC 405547055.{{cite book}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)

[1] Munagala, Kameshwar; Ranade, Abhiram (1999)。「グラフアルゴリズムの I/O 複雑性」。第 10 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録。SODA '99。米国ペンシルバニア州フィラデルフィア: Society for Industrial and Applied Mathematics: 687–694。ISBN 9780898714340。

[2] 「igraph R マニュアルページ」。igraph.org 。 2019年10月16日閲覧。

[khan-3] 「グラフの表現」。カーンアカデミー。 2019年10月16日閲覧。

[4] Kolaczyk, Eric D. (2009-04-20).ネットワークデータの統計分析：方法とモデル. ニューヨーク. pp. 22. ISBN 9780387881461. OCLC 405547055.{{cite book}}: CS1 メンテナンス: 場所が見つかりません発行者 (リンク)