Adjacency listとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Adjacency listの意味・解説 

隣接リスト

(Adjacency list から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/08/06 17:11 UTC 版)

隣接する頂点を付記した無向グラフ。この場合の隣接リストは {2,3}, {1,3}, {1,2,4}, {3} となる。

隣接リスト(りんせつリスト、: adjacency list)は、グラフ理論でのグラフにある頂点または辺を全てリスト(一覧)で表現したものである。

一般に隣接リストでは順序は不定である。

計算機科学での応用

上図のグラフは以下のような隣接リスト表現を持つ:
1 2,3 と隣接
2 1,3 と隣接
3 1,2,4 と隣接
4 3 と隣接

計算機科学において、隣接リストはグラフを表すデータ構造と密接な関係がある。隣接リスト表現では、各頂点について、1つの辺でその頂点とつながっている全ての他の頂点のリストを作る(これがその頂点の「隣接リスト」である)。例えば、ヴァンロッサムが示唆した表現では、各頂点とその隣接する頂点群の配列ハッシュテーブルで関連付ける[1]。これは隣接リスト表現のインスタンスの1つと考えられる。また、Cormen らの表現では、頂点の番号をインデックスとする配列に各頂点の隣接する頂点群の片方向リストへの参照を格納する[2]

隣接リスト構造の問題点は、グラフの辺についてのデータ(例えば、長さ、コストなど)を格納する明確な場所がない点である。その解決策として、例えば Goodrich と Tamassia の著書では、よりオブジェクト指向的に隣接リスト構造を変形し、各頂点に接合する辺を表したオブジェクトのリストを格納するオブジェクト(incidence list と呼ぶ)を提案している[3]。この構造を完成させるには、各辺から2つの端点の頂点への参照を行う必要がある。このバージョンの隣接リストでは、辺オブジェクトが追加されるため、頂点だけをリストにしているものよりもメモリを余分に消費する。しかし、辺に関する情報を格納するには便利である。

トレードオフ

隣接リストの代替としては隣接行列がある。疎らな隣接行列となるグラフの場合、隣接リストの方がメモリを無駄にしない。これは、隣接リストの方が存在しない辺を表すメモリ領域を全く必要としないためである。32ビットのコンピュータ上で単純な配列による隣接リスト実装をすると、無向グラフでは8eバイトのメモリを必要とする。ここで、eは辺の数で、隣接リストでは辺が1つあると2箇所にそれに対応したデータが必要で、1つを4バイトと計算している。

一方、隣接行列では1カ所には1ビットで済むため、非常にコンパクトに表現でき、n2/8バイトしか要しない。ここで、nは頂点の数である。無駄な領域があるとしても、このコンパクトさは参照の局所性という点で好ましい。

n個の頂点のグラフでは、辺は最大でも(ループを許容しても)n2であり、ここで d = e/n2 をグラフの密度とする。すると 8e > n2/8、すなわち隣接リストが隣接行列よりもメモリを消費するのは d > 1/64 のときである。したがって隣接リスト表現がメモリ使用量という面で正当化されるには、グラフが十分に疎らでなければならない。しかし、以上の分析はグラフの連結構造だけを表現する場合の話で、その他の数値情報を格納する場合はまた別の考察が必要である。

メモリ使用量のトレードオフとは別に、データ構造にはそれぞれ適した操作が存在する。ある頂点に隣接する頂点群を探すことは隣接リスト表現では容易であり、単にその頂点の隣接リストを見ればよい。隣接行列では、1つの行全体をスキャンする必要があり、O(n) の時間がかかる。2つの頂点を結ぶ辺があるかどうかを知りたい場合、隣接行列では1回の操作で済むが、隣接リストでは、リストをたどって調べる必要がある。

脚注・出典

  1. ^ Guido van Rossum (1998年). “Python Patterns — Implementing Graphs”. 2009年6月25日閲覧。
  2. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. pp. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7 
  3. ^ Michael T. Goodrich and Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1 

参考文献


「Adjacency list」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Adjacency list」の関連用語

Adjacency listのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Adjacency listのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの隣接リスト (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS