グラフ (データ構造)

グラフとは

グラフは、ノード（頂点）とエッジ（枝）によって構成されるデータ構造です。グラフは、データ間の関連性やネットワーク構造を表現するために用いられ、様々な分野で応用されています。

グラフの基本構造

グラフは、頂点の集合 V と、頂点間の接続を表すエッジの集合 E によって定義されます。形式的には、G = (V, E) と表され、V は有限集合であり、E は V から選ばれた2つの要素のペアの集合です。

グラフの表現方法

グラフをコンピュータ上で表現するための主なデータ構造として、以下の2つが挙げられます。

隣接リスト: 各ノードに対して、隣接するノードのリストを保持します。まばらなグラフ（エッジが少ないグラフ）に適しています。
隣接行列: 行と列にノードを並べた2次元配列で、各要素は2つのノード間にエッジがあるかどうかを示します。密なグラフ（エッジが多いグラフ）に適しています。

エッジに何らかの情報を付加したい場合は、エッジごとのデータ構造が必要になります。また、非常に大きなグラフでエッジに規則性がある場合は、シンボリックグラフという表現も用いられることがあります。

グラフの操作

グラフに関するアルゴリズムは数多く研究されており、様々な操作が可能です。代表的な操作として、2つのノード間の経路探索があります。

深さ優先探索 (DFS) と幅優先探索 (BFS): あるノードから別のノードへの経路を探索するアルゴリズムです。
ダイクストラ法: あるノードから他のすべてのノードへの最短経路を求めるアルゴリズムです。
ワーシャル-フロイド法: すべてのノードの組み合わせについて、それぞれの最短経路を求めるアルゴリズムです。

有向グラフはフローネットワークとして扱うことができ、各エッジに容量が定められ、グラフ上をフローが流れます。

フォード・ファルカーソンのアルゴリズム: グラフの始点から終点への最大フローを求めるアルゴリズムです。

関連技術

グラフに関連する技術として、以下のようなものがあります。

グラフ理論: グラフの数学的な性質を研究する分野です。
シーングラフ: 3次元コンピュータグラフィックスで、オブジェクトの階層構造を表現するのに用いられます。
最短経路問題: 2つのノード間の最短経路を求める問題です。
全域木: グラフのすべてのノードを連結する、ループを持たない部分グラフです。
Graphviz: グラフ構造を可視化するためのソフトウェアです。

外部リンク

Interactive visualisations: グラフなどのデータ構造を視覚化して表示するツールです。

参考文献

Boost Graph Library: C++ 用のグラフライブラリです。
Perl によるグラフルーチン群: Perl でグラフを扱うためのライブラリです。
QuickGraph: .NET 用のグラフライブラリです。
Algraf Project: グラフ描画ツールやアルゴリズム、XML変換ツールなどが含まれたプロジェクトです。
* WordGraph: テキスト構造を解析し、グラフ描画するソフトウェアです。

もう一度検索