グラフ #algorithm

コンピューターで扱う問題は、「対象」とそれらの「関係」を抽象的に示したグラフと呼ばれるデータ行動で示すことができます。グラフは、現実世界の様々な問題をモデル化することができるので、グラフに関するアルゴリズムが多く研究されてきました。

グラフとは、「対象と集合とそれらのつながりの関係の集合」を表すデータ構造です。

クラブにおける「対象」はノードまたは頂点と呼ばれ、一般的に円で表されます。「つながり」は頂点と頂点の関係を表し、エッジまたは辺と呼ばれ、円と円を結ぶ線または矢印で表されます。

グラフは主に４種類

有向グラフのエッジは2つの頂点間のつながりの有無を示すだけでなく、つながりに方向があり、エッジをつなぐ視点と終点を区別します。重み付きグラフでは、各エッジに値が割り当てられます。

頂点の集合がV、辺の集合がEであるようなグラフ
- G = (V, E)
- 頂点と辺の数は|V|,|E|と表す。
２つの頂点を結ぶ辺
- e = (u, v)
- 無向グラフの場合(u, v)と(v, u)は同じ辺を示す。
- 重み付きグラフの辺(u, v)の重みをw(u, v)と示す。
無向グラフに辺(u, v)があるとき、頂点uと頂点vは隣接している(adjacent)と言う。隣接している頂点の列v0,v1,v2,v3.....vkをパス(path)と言います。
始点と終点が同じようなパスを閉路(cycle)と言います。
閉路のない有向グラフをDirected Acyclic Graph(DAG)と呼びます。

頂点uに繋がっている辺の数を頂点uの次数(degree)と言います。有向グラフにおいては、頂点uに入る辺の数を頂点uの入次数、頂点uから出る辺の数を頂点uの出次数と言います。
例えば、図のDAGグラフの頂点3の入次数は３、出次数は1です。

グラフG = (V, E)の任意の２つの頂点u, vに対して、uからｖへパスが存在するとき、Gを連結なグラフと言います。

2つのグラフGとGについて、Gの頂点集合と辺集合の両方がGの頂点集合と辺集合の部分集合になっているとき、G`をGの部分グラフと言います。

グラフにおける最も基本的なアルゴリズムが探索です。グラフの探索とは、グラフの全ての頂点、または部分的な頂点の集合、を体系的に訪問することです。。訪問の仕方によってグラフの様々な特徴を調べることができるので、多くの重要なアルゴリズムの基礎となっています。

グラフにおける代表的な探索アルゴリズムが深さ優先探索(DFS: Depth First Search)と幅優先探索(BFS: Breadth First Search)で、無向グラフと有向グラフのどちらにも適用されます。

深さ優先探索は、「行けるところまでとことん行く」というルールに従った、グラフにおける最も自然で基本的な探索アルゴリズムです

一方、幅優先探索は既に探索した頂点と未探索の。頂点の境界を幅いっぱいにわたって拡張しながら探索します。幅優先探索は最短経路を求めるアルゴリズムの1つとして応用することができます。