|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 隣 : [となり] 【名詞】 1. next to 2. next door to ・ 隣接 : [りんせつ] 1. (n,vs) adjoin 2. adjacent 3. related
隣接リスト(英: adjacency list)は、グラフ理論でのグラフにある頂点または辺を全てリスト(一覧)で表現したものである。 一般に隣接リストでは順序は不定である。 == 計算機科学での応用 == 計算機科学において、隣接リストはグラフを表すデータ構造と密接な関係がある。隣接リスト表現では、各頂点について、1つの辺でその頂点とつながっている全ての他の頂点のリストを作る(これがその頂点の「隣接リスト」である)。例えば、ヴァンロッサムが示唆した表現では、各頂点とその隣接する頂点群の配列をハッシュテーブルで関連付ける。これは隣接リスト表現のインスタンスの1つと考えられる。また、Cormen らの表現では、頂点の番号をインデックスとする配列に各頂点の隣接する頂点群の片方向リストへの参照を格納する。 隣接リスト構造の問題点は、グラフの辺についてのデータ(例えば、長さ、コストなど)を格納する明確な場所がない点である。その解決策として、例えば Goodrich と Tamassia の著書では、よりオブジェクト指向的に隣接リスト構造を変形し、各頂点に接合する辺を表したオブジェクトのリストを格納するオブジェクト(incidence list と呼ぶ)を提案している。この構造を完成させるには、各辺から2つの端点の頂点への参照を行う必要がある。このバージョンの隣接リストでは、辺オブジェクトが追加されるため、頂点だけをリストにしているものよりもメモリを余分に消費する。しかし、辺に関する情報を格納するには便利である。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「隣接リスト」の詳細全文を読む スポンサード リンク
|