TechFULの中の人

triple-four’s blog

グラフのキホン(2)表現方法と探索編

こんにちは!TechFULでアルバイトをしているSiiiecです。       

前回記事ではグラフの概要について扱いました。   今回は、グラフの表現方法探索について解説します!

グラフの表現方法

グラフ構造をプログラムで扱うには、隣接行列隣接リストの2種類のデータ構造があります。
以下説明のため、頂点集合をV、辺の集合を E、頂点・辺の数をそれぞれ |V|, |E|と表します。

隣接行列

|V| \times |V|の大きさの行列Mを使い、頂点uと頂点vを繋ぐ辺の情報をM_{u, v}で表します。
例えば、頂点iから頂点jへ向かう辺が存在する場合 M_{i, j} = 1、存在しない場合M_{i, j} = 0と表すことができます。

f:id:siiiec:20190211141035j:plain:w250 f:id:siiiec:20181222154336j:plain:w250
隣接行列

  • 無向グラフは、双方向に繋がっている有向グラフと扱えるので、 M_{u, v} = M_{v, u}として表すことができます。
  • 重みつきグラフは、各成分を01ではなく辺のコストとして表すことができます。
特徴
  • 辺の数が少ない場合でも、|V| \times |V|のメモリが必要になります。
  • 辺が存在するかどうかは、O(1)と高速に判定できます。

隣接リスト

各辺から行くことのできる辺をリスト形式で表します。
リストの配列といった形式で表すことが多いです。

f:id:siiiec:20190211140653j:plain:w250 f:id:siiiec:20181222154336j:plain:w250
隣接リスト

特徴
  • 必要なメモリは|E| + |V|のみとなります。
  • 辺が存在するかどうかの判定には、繋がっている頂点を全て調べる必要があります。

グラフの探索

深さ優先探索

新しく見つけた頂点を優先して探索します。
スタックを用いることで実現できます。

ある木を探索する場合、一例としてこのような順序で探索を行います。
f:id:siiiec:20181222162135p:plain:w250

幅優先探索

先に見つけた頂点を優先して探索します。
キュー(待ち行列)を用いることで実現できます。

この場合は、一例としてこのような順序で探索を行います。
f:id:siiiec:20181222162139p:plain:w250

おわりに

全2回でグラフの基礎部分について扱いました。
グラフのイメージを掴んでもらえると嬉しいです!

Siiiecでした!

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp