グラフと木の違い
グラフ
グラフ (gragh) は、いくつかの頂点 (vertex) と、それらを結ぶいくつかの辺 (edge) から構成される。
辺が向きを持たないものを 無向グラフ 、向きを持つものを 有向グラフ と呼ぶ。
木
木は基本的には無向グラフの一種となる。無向グラフの内、以下のような条件を満たすものを 木 と呼ぶ。
- 根 (root) と呼ばれる特別な頂点が 1 つだけ存在する。
- すべての頂点から根に至る単純道が唯一存在する。
2 つ目の条件は「 連結で閉路がない 」ことと同値である。
もっとざっくばらんに表現すると、「根が一つだけ存在し、それぞれの頂点が親を 1 つのみ持つ無向グラフ」のことを木と呼ぶ。