データ構造とアルゴリズム第6回の2 木～データ構造（3）～ 1 木構造 (tree) 2 内容    グラフ木構造木の定義と用語       根，節点，葉親子，兄弟，先祖，子孫経路と経路の長さ深さと高さ木の走査代表的な木構造 3 グラフ(graph)     有限個の節点( の集合で構成される V：（）の集合 E：（）の集合 G：（） )と，エッジ( ) 節点 v1 辺 (枝) e = (v1, v2) v2 4 無向グラフと有向グラフ  (undirected graph) 枝に方向を考えないグラフ (v1, v2) = (v2, v1) 1 v2 v  (directed graph, digraph) 枝の方向を考えるグラフ (v1, v2) ≠ (v2, v1) v1 v2 v2 v1 アーク 5 完全グラフ(complete graph)  すべての節点対の間に枝をもつ無向グラフ 6 部分グラフ(subgraph)  グラフG = (V, E)に対し，（），（）の作る G’=(V’, E’)がグラフであるとき，G’はGの（）であるという 7 経路(path)     v1から v3への経路は存在する P: v1, v2,v3 v1から v4への経路は存在しない経路P: v1, v2,v3は節点がすべて異なる⇒（）経路P: v1, v2,v3,v1は始点と終点が等しく、その他の節点はすべて異なる⇒（） v4 v2 v1 v3 v5 v6 v7 8 ケーニヒスベルグの橋陸地が4つ橋が7本同じ橋を2度渡らずにすべての橋を通ってもとの場所に戻れるか節点が4つ辺が7本同じ辺を2度通らずにすべての辺を通ってもとの節点に戻る経路はあるか 9 連結グラフ(connected graph)   連結グラフ：任意の2つの節点間に経路が存在する無向グラフ無向木：閉路を持たない連結無向グラフ 10 木（Tree）葉 leaf 根 root 12 階層構造（hierarchical structure）  木構造は，階層的な関係を表現するのに適している A大学 C学部 B学部 D学科 E学科 F学科 G学科 H学科 Iコース 14 階層構造の例  組織図  系図  階層ディレクトリ (p.39 図2.16) etc... 15 木の再帰的定義 (1) 単一の節点は， (1)’ 空集合でも木（ (2) Ti : 木 ni : 木Tiの根 n : すべてのniの親新しい木ができる Tiは新しい木の nは新しい木の根 (3) すべての木は，得られる (p.42) ） n n1 n2 nk T1 T2 Tk 16 問題  a 右図は木といえるか？ ⇒  右図のような構造をという c b d e f g h 17 兄弟 a 同じ親を持つ節点を（sibling）という    bとは兄弟ｃととは兄弟 gとは兄弟 c b d f e g h i 19 経路と経路の長さ  ｎ1，ｎ2，・・・，ｎk が木の中の節点の列であって，１≦ｉ＜ｋに対してｎi がｎi+1の親になっているとき，この列のことを「節点ｎ1から節点ｎk への (path)」という．  このとき，経路の長さは k -1  節点自身への経路の長さは０ n1 n2 n3 20 先祖と子孫    節点ａから節点ｂへの経路があるとき，ａはｂの (ancestor)，ｂはａの (descendant)であるというどの節点も自分自身の先祖であり子孫である自分自身以外の先祖や子孫をという 21 例1 経路と子孫  aからhへの経路：  その経路の長さ：  ｆの子孫： a b c  d f e g i ｆの真の子孫： h 22 例2 先祖 a   ｃの先祖 b ｃの真の先祖根（ｒoot） ⇒  葉（leaf） ⇒ c d f g e i  節点節点 h 23 深さと高さ  節点の高さ（height）ある節点から  木の高さ木の  節点の深さ(level, depth) 根から 24 例3 深さと高さ  a 節点b 高さ，深さ深さ（レベル）０ b  節点g 高さ，深さ c  f d e g i 木の高さ h 25 順序木と無順序木   順序木（ordered tree）：兄弟間で順序づけを行った木無順序木(unordered tree)：子の順序を無視した木 a b 無順序木としてみれば，同じ木 c c 順序木としてみると，異なる木左： bが，cが右： cが，bが a b 26