pikesaku’s blog

個人的なプログラム勉強メモです。記載内容について一切の責任は持ちません。

データ構造としてのグラフとは?

グラフとは?

 
ノードとエッジで表現するデータ型
ノードは頂点
エッジはノード間の連結関係を示す
グラフ理論を適用できる
mathtrain.jp

 

グラフの数学的表現方法

以下の2つがあり。
 

①隣接行列

 
以下URLより引用
隣接行列 — WTOPIA v1.0 documentation
 

行列という名の通り, グラフを 2 次元配列で表現する. 配列のインデックスがノードの番号に対応する. 例えば, この 2 次元配列を M とすると, M[i][j] がノード i と ノード j の関係を表す

f:id:pikesaku:20170716223645p:plain

 
連結の向き・重みを考慮した場合の表現もある。
 

②隣接リスト

 
以下URLより引用
mathwords.net
 

f:id:pikesaku:20170716224306p:plain

 

グラフ表現の例

 
tech-blog.abeja.asia
グラフ表現
 
画像や文章の表現も可能。
画像表現に適しているが、グラフ構造を処理するには、計算量が莫大になる問題があり。
 
※Convolution=畳み込み(難しい。。。)
qiita.com