グラフとは

グラフとは、オブジェクトの集合の中にある関係性を表現するために使われる、数学的な抽象性があるものです。

ノードとエッジ

グラフの中のオブジェクト(要素)のことを「ノード」と言います。
オブジェクト間の関係性を示すもののことを「エッジ」と言います。

普段からよく使うファイルシステムも一種のグラフと言えるそうです。ディレクトリ(フォルダ)とそれぞれのファイルは、ノードとして扱われます。また、それぞれのファイルがどのディレクトリに属しているかの情報は、エッジということですね！

参考にした記事はこちらになります。https://proto.school/merkle-dags/03
画像もあるのでわかりやすいです！

有向グラフ

方向を持つグラフを「有向グラフ」と言います。通常のファイルシステムも有向グラフの一つです。あるディレクトリに属しているディレクトリが、その親ディレクトリを含んでいることはないということです。

１方向の依存関係で成り立っているグラフってことか。

有向グラフの用語紹介です。

• ルートノード(root node) 親がないノード、最上層のノード
• 葉ノード(leaf node) 子がないノード
• 中間ノード (intermidiate node)　親と子の両方を持つノード
• 非葉 (non-leaf) ルートノードと中間ノードの両方を指し示すノード

非巡回グラフ

グラフにループがない場合に、「非巡回グラフ」と言えます。グラフ内ノードとエッジをたどって、そのノード自体に辿り着くことができないグラフのことです。

有向非巡回グラフ

有効グラフと非巡回グラフの両方の特徴を持つグラフです。

とても有名で、このテーマについて数多くの研究がなされているようです。そのため、略称として『DAG』(Directed Acyclic Graph)が使用されます。

これが有向非巡回グラフにピッタリ！

家系図は、まさにDAGで表すのに適したデータセットですね！

• 自分自身が自分の親(先祖)になることはできない。
• 子が親を産むことはできない(あまりに当たり前すぎて直感的ではないですが、そういうことです！)

今回は、DAGとその周辺の用語をメモしました。忘れかけたり、追加があれば追加していきます。