この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。

万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。

信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。

履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。

翻訳後、{{翻訳告知|en|Graph (abstract data type)|…}}をノートに追加することもできます。

Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

6個の頂点と7本の枝からなるラベル付きグラフ

グラフ（英: 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 - タブインデントで記述されたテキストの構造を解析し、グラフ描画するソフト。

表

話

編

歴
データ構造
その他

コレクション(英)

コンテナ

代数的データ型

素集合データ構造

永続データ構造

並行データ構造(英)

配列構造(英)

配列

可変長配列

ビット配列(英)