隣接リスト表現,グラフの

• V個のノードについて、それが隣接するノードをリストに列挙する方法。無向グラフの場合には、隣接ノードの種類は１つであり、１エッジの読み込みにつき、２つの端ノードの両方について、隣接ノードを追加し、有向グラフの場合には、隣接ノードの種類は２種類(上流か下流か)であり、１エッジの読み込みにつき、２つの端ノードの両方について、かたや、上流ノードをかたや下流ノードを追加する。１エッジが２ノードに登録されることによって、探索が効率的に行える。出来上がる隣接リストはエッジ情報の入力情報に依存する。したがって、入力順序は処理論理の効率に影響を与える。また、解が複数存在する場合には、最初に得られる解が、入力順序によって異なることもありえる。
• ノードとその連結エッジの除去処理は、隣接リスト表現ではステップ数が多くなる。煩雑さを回避するためには、登録された隣接ノード同士にリンクを張る方法があるが、こうすることで、すばやく処理できるが、体系自体は煩雑になる。