グラフ (データ構造)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/24 19:09 UTC 版)
 | この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
グラフ（英: Graph）とは、ノード（頂点）群とノード間の連結関係を表すエッジ（枝）群で構成される抽象データ型、and・orその実装である具象データ型である。グラフ理論を基盤として、なんらかの証明が可能であったり、豊富なアルゴリズムが利用できること、などが特徴である。
グラフは G=(V,E) で表され、V は頂点（vertices）の集合、E は頂点と頂点をつなぐエッジ（edges）の集合である。形式的には、グラフ G は順序対 G=(V,E) で定義され、V は有限の集合、E は V から選んだ2つの元からなる集合の集合である。
表現の選択肢
グラフを実際に表現するための主なデータ構造として、2種類のデータ構造がある。第一は隣接リストと呼ばれるもので、各ノード毎に隣接するノードのリストを保持するデータ構造である。第二は隣接行列と呼ばれるもので、行と列にエッジの始点と終点となるノードが並んだ2次元の配列で表され、配列の各要素は2つのノード間にエッジがあるかどうかを示す値が格納される。隣接リストはまばらなグラフに適しており、そうでない場合は隣接行列の方が望ましい。アルゴリズム上の要請から、何らかの情報をエッジに持たせる必要がある場合など、エッジごとのデータがあるデータ構造が必要な場合もある。非常に大きなグラフでエッジに何らかの規則性がある場合、シンボリックグラフという表現も選択肢としてありうる。
操作
グラフに関するアルゴリズムは数多く、よく研究されている。グラフに関する典型的な操作としては、2つのノード間の経路を探す操作がある。深さ優先探索や幅優先探索のような手法を使い、あるノードから別のノードへの最短経路を求める。例えば、ダイクストラ法がある。全てのノードの組合せについてそれぞれの最短経路を求めるワーシャル-フロイド法もある。
有向グラフはフローネットワークとして見ることができ、各エッジに容量が定められ、何らかのフローがグラフ上を流れる。グラフの始点から終点への最大フロー問題を解くアルゴリズムとしては、フォード・ファルカーソンのアルゴリズムがある。
関連項目
外部リンク
- Interactive visualisations グラフなどのデータ構造を視覚化して表示（Mozilla Firefoxでは動作しない）
- Notes
- Boost Graph Library C++ 用の強力なグラフライブラリ
- Perl によるグラフルーチン群
- QuickGraph: Graph Data Structures And Algorithms for .NET
- Algraf Project グラフ描画ツール、いくつかのグラフ関連アルゴリズム、XMLへの変換など
- WordGraph - タブインデントで記述されたテキストの構造を解析し、グラフ描画するソフト。
「グラフ (データ構造)」の例文・使い方・用例・文例
- 棒グラフ
- 折れ線グラフ
- 新しいパラグラフで書き出しなさい
- このグラフは若者による犯罪の急激な増加を示します
- 彼が下のグラフを見る
- 弊社がメカニカルクロノグラフモデル１機種を１月２５日より全国で発売します
- 社外のグラフィッカーにデザインを発注する予定だ。
- 新しいコロナグラフがついに完成した。
- 多機能クロノグラフ
- 彼女はお気に入りの歌手のディスコグラフィーをダウンロードした。
- QC7つ道具は、特性要因図、チェックシート、ヒストグラム、散布図、パレート図、グラフ ・層別の7つがある。
- 消費者行動を分析する際は、アンケート調査によるサイコグラフィック変数も加味する必要がある。
- ペイオフダイアグラムでは戦略の採算性をグラフを用いて表す。
- 宗教や人種的背景は、いくつかの国に存在するが他の国には存在しないデモグラフィック変数の例である。
- 私の母はうつ病の疑いがあるので、光トポグラフィー検査を受けに行きます。
- 民族学者を育成し、民俗学研究を推進するため、ABC大学にエスノグラフィー・センターが設立された。
- 下記グラフは20代後半の女性の平均消費性向を示している。
- 「棒足」は上に高値を、下に安値を示している棒グラフのことである。
- 下記グラフは名目所得の推移を示している。
- 私は日本に滞在しながら、ファッションフォトグラファーの仕事をしています。
グラフ_(データ構造)と同じ種類の言葉
- グラフ_(データ構造)のページへのリンク
