TechFULの中の人

triple-four’s blog

グラフのキホン(1)グラフ概要編

こんにちは!TechFULでアルバイトしているSiiiecです。
このシリーズでは、全2回に分けて、プログラミングで頻出するグラフの基本について解説したいと思います。

今回は、グラフの概要についてです!

グラフとは

早速Wikipediaで見てみましょう。

グラフ (データ構造) - Wikipedia

グラフは G=(V,E) で表され、V は頂点(vertices)の集合、E は頂点と頂点をつなぐエッジ(edges)の集合である。形式的には、グラフ G は順序対 G=(V,E) で定義され、V は有限の集合、E は V から選んだ2つの元からなる集合の集合である。

文字だけでは分かりにくいので、実例を紹介します。

f:id:siiiec:20181220103644p:plain:h200
こんなものや、
f:id:siiiec:20181220103714p:plain:h200
こんなものがグラフです。

イメージが湧いたでしょうか?
上の図では丸い部分が頂点、頂点同士を結ぶ線が辺(エッジ)です。

有向グラフと無向グラフ

上の図では、辺に向きがあるものと向きがないものがありました。
辺に向きが設定されているグラフを有向グラフ、向きが設定されていないものを無向グラフと呼びます。

名前のとおりですね!

無向グラフを、双方向に辺が張ってある有向グラフと捉えることで統一的に扱うことができます。

重みつきグラフ

上の例では、辺は頂点同士を繋いでいるかどうか、という情報しか分かりませんでした。
しかしそれだけではなく、「ある道(辺)で行くとM分かかる」というように、辺自体にコスト(重み)を持たせて考える場合があります。

この場合はかかる時間が重みとなります。
このような重みのついたグラフを、重みつきグラフと呼びます。

またまた名前のとおりですね!

連結と非連結

これも名前のとおりです!

全ての頂点同士が繋がっている(任意の頂点からいくつかの辺を辿って他のすべての頂点に辿り着ける)ようなグラフを連結、そうでないものを非連結と呼びます。

f:id:siiiec:20181220110305p:plain:h250
連結グラフ(左)と非連結グラフ(右)

閉路

頂点の辿り方を、パスと呼びますが、始点と終点が同じようなパスを閉路と呼びます。 f:id:siiiec:20181220110912p:plain:h250

連結であり、閉路のないグラフをと呼びます。 木には、頂点数 - 1個の辺が存在します。
言い換えると、頂点数 - 1個の辺が存在し、連結なグラフは木であるとも言えます。

ファイル階層を表した図は、木の典型的な例です。

おわりに

グラフについてのイメージを掴むことができたでしょうか?
次回の記事では、グラフのデータ構造と、探索方法について解説します。

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp