有向グラフ(Directed Graph)は、計算機科学の分野では頻出のグラフのデータ構造です。
有向グラフを用いることで、実世界のさまざまなオブジェクトやオブジェクト間の関係性を表現することができます。
身近な例では、人間をグラフの頂点とし、人間関係やその親密度をエッジで表現することでソーシャルネットワーク上の関係性を示すことや、ネットワーク構造、そのほか、交通網であったり、ものごとの因果関係など、物理・論理的なもの問わず、多くの物事のモデル化に利用されます。
グラフ構造自体は、実用的なものを何か実装する際にはいつか身につける必要性がありますし、その他競技プログラミングなどでも多く登場します。
今回はグラフ構造における、有向グラフ(Directed Graph)についてわかりやすく解説していきます。
また有向グラフをプログラミングで表現するためのデータ構造として隣接行列についても解説していきます。
グラフ構造を簡単におさらい
グラフは、頂点と辺の集合からなるオブジェクトです。よく、教科書等では、下記のような図形とともに、グラフ構造が紹介されます。
上図における頂点(黒丸)で描かれているところを頂点(vertex)と呼び、$V$で表現し、頂点を結んでいる線が辺(edge)で、$E$と表現します。
またグラフ自体は$G$で表現し、$G$は$V$と$E$の集合で構成されることから、グラフそのものを$G=(V, E)$と表現します。
グラフ構造を扱う場合は、頂点だけでなく、辺にも注目することが多いため、辺も明示的に示したのが上図になります。この構造における、集合としての$V$、$E$の要素は、上図の場合だと次のようになります。
V = \{ A, B, C, D, E, F\} \\
E = \{ e_1, e_2, e_3, \cdots, e_{10}\} \\
e_1 = (A, B), e_2 = (B, C) , \cdotsちなみに、頂点同時がエッジによって結ばれている状態を、頂点同士が隣接していると表現します。また、頂点とエッジが結合している状態を、接続されていると表現します。
有向グラフについて解説
グラフ構造について、概要を抑えたので、続いて有向グラフについて解説します。
こちらも図形で示した方が早いので、まず有向グラフを図形で示します。
先ほど、グラフの例で出した図形とほとんど似ていますが、辺に注目すると、各頂点を結んでいる辺が矢印に変わっていることに気づくと思います。
有向グラフは、グラフ構造の辺に向きを持たせたグラフ構造になります。それ以外は通常のグラフと何ら変わりありません。
有向グラフ(Directed Graph)を隣接行列で表現する
続いて、有向グラフをプログラミングする場合、どのようなデータ構造を用いるかについて解説します。
有向グラフを表現するのに、実用的に持ちられるのは隣接行列(adjacency matrix)です。隣接行列は、正方行列を用いて、各頂点と辺の関係性を表現したものとなっています。
こちらについては、文字で解説するよりも、絵で見た方が遥かに理解しやすいので、まず下図をご覧ください。
左側が有向グラフで、右側が有向グラフを表現した隣接行列です。
右側の行列が隣接行列になります。隣接行列を$A$で表現すると、$A$の成分$A(i, j)$は次のようになります。
A(i, j ) =
\begin{cases}
1 & (e_i, e_j) \in E \\
0 & (e_i, e_j) \notin E
\end{cases}このような隣接行列を用いることで、有向グラフを表現することができます。
行列の値と辺の関係性がいまいち理解できないと思うので、それらの対応を色付けした図が下記になります。
$e_1 = (A, B)$ に対応する辺が、隣接行列における(0, 1) 成分に対応しているのがわかります。
有向グラフの表現として隣接行列だけでなく、隣接リストを用いた表現もありますが、その解説は別の記事でまとめたいと思います。