隣接リストとは？
隣接リストとは、グラフを表すとき、頂点ごとに「その頂点から辺でつながっている頂点」の一覧を持たせる表現方法。必要な記憶量が辺の本数に比例するため、頂点が多く辺が少ない疎なグラフに向く。
りんせつりすと
隣接リストの意味
グラフを表すとき、頂点ごとに「その頂点から辺でつながっている頂点」の一覧を持たせる表現方法。必要な記憶量が辺の本数に比例するため、頂点が多く辺が少ない疎なグラフに向く。
隣接リストの具体例
交友関係のように、利用者が数百万人いても1人あたりのつながりは数百人という場合。全員分の総当たり表を持つと現実的な容量に収まらないので、各利用者に相手の一覧をぶら下げる形で保持する。
隣接リストは試験でどう引っ掛けられる？
2つの頂点がつながっているかを調べる操作は、総当たり表なら一定時間だが隣接リストでは一覧をたどるので遅い。記憶量が小さいから常に有利なのではなく、操作ごとに得意不得意がある。
隣接リストと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。