グラフ (データ構造)
グラフを実際に表現するための主なデータ構造として、2種類のデータ構造がある。第一は隣接リストと呼ばれるもので、各ノード毎に隣接するノードのリストを保持するデータ構造である。第二は隣接行列と呼ばれるもので、行と列にエッジの始点と終点となるノードが並んだ2次元の配列で表され、配列の各要素は2つのノード間にエッジがあるかどうかを示す値が格納される。隣接リストはまばらなグラフに適しており、そうでない場合は隣接行列の方が望ましい。アルゴリズム上の要請から、何らかの情報をエッジに持たせる必要がある場合など、エッジごとのデータがあるデータ構造が必要な場合もある。非常に大きなグラフでエッジに何らかの規則性がある場合、シンボリックグラフという表現も選択肢としてありうる。