グラフ (データ構造)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
6個の頂点と7本の枝からなるラベル付きグラフ

グラフ: Graph)とは、計算機科学において、ノード(頂点)群とノード間の連結関係を表すエッジ(枝)群で構成される抽象データ型の一種である。グラフ抽象データ型は、数学におけるグラフ理論に基づいている。

グラフは G=(V,E) で表され、V は頂点(vertices)の集合E は頂点と頂点をつなぐエッジ(edges)の集合である。形式的には、グラフ G は順序対 G=(V,E) で定義され、V は有限の集合、EV から選んだ2つの元からなる集合の集合である。

表現の選択肢[編集]

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

他のデータ構造との比較[編集]

グラフデータ構造は階層的ではないため、個々の要素が複雑に絡み合っているようなデータを表現するのに適している。例えば、コンピュータネットワークはグラフとして表現するのに適している。

階層的なデータは二分木二分木以外の木構造で表される。ただし、木構造はグラフ構造の特殊ケースと見ることもできる。

操作[編集]

グラフに関するアルゴリズムは数多く、よく研究されている。グラフに関する典型的な操作としては、2つのノード間の経路を探す操作がある。深さ優先探索幅優先探索のような手法を使い、あるノードから別のノードへの最短経路を求める。例えば、ダイクストラ法がある。全てのノードの組合せについてそれぞれの最短経路を求めるワーシャル-フロイド法もある。

有向グラフはフローネットワークとして見ることができ、各エッジに容量が定められ、何らかのフローがグラフ上を流れる。グラフの始点から終点への最大フロー問題を解くアルゴリズムとしては、フォード・ファルカーソンのアルゴリズムがある。

関連項目[編集]

外部リンク[編集]