グラフの定義
グラフ (Graph) とは [対象の集合
と, それらのつながりの集合] を表すデータ構造で, 様々な問題に応用される. 現実世界のあゆゆる問題をモデル化することができるので, グラフに関する重要なアルゴリズムが数多く存在する.
簡単なグラフの例を以下に示す.
[対象] は ノード (node) またはバーテックス (vertex) と呼ばれ, 上図の円に相当する.
[つながり] はノードとノードの関係を表し, エッジ (edge) と呼ばれ, 上図で円と円を結んでいる線に相当する.
グラフには様々な種類があり, 問題によって応用の方法も違ってくる.