グラフ（英: Graph）とは、ノード（頂点）群とノード間の連結関係を表すエッジ（枝）群で構成される抽象データ型、and・orその実装である具象データ型である。グラフ理論を基盤として、なんらかの証明が可能であったり、豊富なアルゴリズムが利用できること、などが特徴である。
グラフは G=(V,E) で表され、V は頂点（vertices）の集合、E は頂点と頂点をつなぐエッジ（edges）の集合である。形式的には、グラフ G は順序対 G=(V,E) で定義され、V は有限の集合、E は V から選んだ2つの元からなる集合の集合である。 グラフを実際に表現するための主なデータ構造として、2種類のデータ構造がある。第一は隣接リストと呼ばれるもので、各ノード毎に隣接するノードのリストを保持するデータ構造である。第二は隣接行列と呼ばれるもので、行と列にエッジの始点と終点となるノードが並んだ2次元の配列で表され、配列の各要素は2つのノード間にエッジがあるかどうかを示す値が格納される。隣接リストはまばらなグラフに適しており、そうでない場合は隣接行列の方が望ましい。アルゴリズム上の要請から、何らかの情報をエッジに持たせる必要がある場合など、エッジごとのデータがあるデータ構造が必要な場合もある。非常に大きなグラフでエッジに何らかの規則性がある場合、シンボリックグラフ グラフに関するアルゴリズムは数多く、よく研究されている。グラフに関する典型的な操作としては、2つのノード間の経路を探す操作がある。深さ優先探索や幅優先探索のような手法を使い、あるノードから別のノードへの最短経路を求める。例えば、ダイクストラ法がある。全てのノードの組合せについてそれぞれの最短経路を求めるワーシャル-フロイド法もある。 有向グラフはフローネットワークとして見ることができ、各エッジに容量が定められ、何らかのフローがグラフ上を流れる。グラフの始点から終点への最大フロー問題を解くアルゴリズムとしては、フォード・ファルカーソンのアルゴリズムがある。
表現の選択肢
操作
関連項目
グラフ理論
シーングラフ
最短経路問題
全域木
Graphviz
外部リンク
⇒Interactive visualisations グラフなどのデータ構造を視覚化して表示（Mozilla Firefoxでは動作しない）
⇒Notes
⇒Boost Graph Library C++ 用の強力なグラフライブラリ
Perl によるグラフルーチン群
⇒QuickGraph: Graph Data Structures And Algorithms for .NET
⇒Algraf Project グラフ描画ツール、いくつかのグラフ関連アルゴリズム、XMLへの変換など
⇒WordGraph - タブインデントで記述されたテキストの構造を解析し、グラフ描画するソフト。
表
話
編
歴
データ構造
その他
コレクション(英)
コンテナ
代数的データ型
素集合データ構造
永続データ構造
並行データ構造(英)
配列構造(英)
配列
可変長配列
ビット配列(英)
接尾辞配列
スタック
キュー
両端キュー
リングバッファ
疎行列
リンク構造(英)
連結リスト
スキップリスト
展開リスト
XOR連結リスト
優先度付きキュー
検索構造(英)
連想配列
ハッシュテーブル
ハッシュ配列木(英)
ハッシュ関数
コンシステントハッシュ法
分散ハッシュテーブル
連想リスト(英)
木構造
二分木
二分探索木
二重連鎖木
デカルト木(英)
トップ木(英)
T木(英)
平衡二分木
AA木
AVL木
赤黒木
スプレー木
スケープゴート木
ツリープ
2-3木
2-3-4木
フィンガーツリー
B木
B+木
B*木
Bx木(英)
UB木(英)
ダンス木(英)
H木(英)
X木(英)
M木(英)
トライ木
基数木
接尾辞木
三分探索木
Cトライ(英)
X-fastトライ(英)
Y-fastトライ(英)
ハッシュ木(英)
BSP木
四分木
八分木
インターバル木
レンジ木(英)
セグメント木(英)
カバー木(英)
メトリック木(英)
BK木(英)
kd木
暗黙k-d木(英)
vp木(英)
R木
R+木(英)
R*木(英)
ヒルベルトR木(英)
優先R木(英)
多重木
多分木(英)
三分木(英)
スパゲッティスタック
フェニック木
リンクカット木(英)
フュージョン木(英)
ヴァンエムデボアス木(英)
指数木(英)
SPQR木(英)
PQ木(英)
(a,b)木(英)
ヒープ
二分ヒープ
三分ヒープ(英)
D分ヒープ(英)
二項ヒープ
2-3ヒープ(英)
Beap(英)
フィボナッチヒープ
左翼ヒープ(英)
ペアリングヒープ(英)
傾斜ヒープ(英)
ソフトヒープ(英)
ウィークヒープ(英)
グラフ構造
有向グラフ
有向非巡回グラフ
二分決定グラフ
ハイパーグラフ
有向非巡回ワードグラフ(英)
抽象データ型