グラフの表現方法 #

グラフはコード上でどのように表現して作ればよいのか？

ここではいくつか方法を示す。

隣接行列 #

まずは隣接行列という方法について。

グラフの頂点の数をVとしたときに初期値が全て0、大きさ|V|*|V|の２次元リスト(行列)Gを用意し、頂点iと頂点jが結ばれているときにG[i][j]、G[j][i]を1にする、という形でグラフを表現する方法である。なお、有向グラフの場合は有効な方向のみに1を設定し、重み付きグラフのときは1ではなく具体的な重みの値を入力する、という形で表現できる。

隣接行列はある2頂点が辺で結ばれているかがすぐわかるという利点があるが、|V|*|V|のリストを作るため、頂点の数が多く辺の数が少ないとリストの大きさや使われない領域がかなり大きくなってしまい、無駄にメモリを利用してしまうという欠点がある。

隣接リスト #

次に隣接リストという方法についてを述べる。

隣接リストはリストのi番目の要素にグラフの頂点iが結んでいる頂点のインデックスのリストを入れたものである。
隣接行列と比べると、辺で結ばれていない頂点のデータが無いため、メモリ量が節約できる。

他にも方法はある？と思うが、見つかったら随時追記いたします・・。