グラフ (データ構造)

グラフ（英: Graph）とは、ノード（頂点）群とノード間の連結関係を表すエッジ（枝）群で構成される抽象データ型、and・orその実装である具象データ型である。グラフ理論を基盤として、なんらかの証明が可能であったり、豊富なアルゴリズムが利用できること、などが特徴である。
グラフは "G=(V,E)" で表され、"V" は頂点（vertices）の集合、"E" は頂点と頂点をつなぐエッジ（edges）の集合である。形式的には、グラフ "G" は順序対 "G=(V,E)" で定義され、"V" は有限の集合、"E" は "V" から選んだ2つの元からなる集合の集合である。
表現の選択肢.
グラフを実際に表現するための主なデータ構造として、2種類のデータ構造がある。第一は隣接リストと呼ばれるもので、各ノード毎に隣接するノードのリストを保持するデータ構造である。第二は隣接行列と呼ばれるもので、行と列にエッジの始点と終点となるノードが並んだ2次元の配列で表され、配列の各要素は2つのノード間にエッジがあるかどうかを示す値が格納される。隣接リストはまばらなグラフに適しており、そうでない場合は隣接行列の方が望ましい。アルゴリズム上の要請から、何らかの情報をエッジに持たせる必要がある場合など、エッジごとのデータがあるデータ構造が必要な場合もある。非常に大きなグラフでエッジに何らかの規則性がある場合、シンボリックグラフという表現も選択肢としてありうる。
操作.
グラフに関するアルゴリズムは数多く、よく研究されている。グラフに関する典型的な操作としては、2つのノード間の経路を探す操作がある。深さ優先探索や幅優先探索のような手法を使い、あるノードから別のノードへの最短経路を求める。例えば、ダイクストラ法がある。全てのノードの組合せについてそれぞれの最短経路を求めるワーシャル-フロイド法もある。
有向グラフはフローネットワークとして見ることができ、各エッジに容量が定められ、何らかのフローがグラフ上を流れる。グラフの始点から終点への最大フロー問題を解くアルゴリズムとしては、フォード・ファルカーソンのアルゴリズムがある。