グラフ、木、木のなぞり。 

July 20 [Mon], 2009, 17:14

/*グラフ*/
有限集合E⊆V×V 二つの節点を結ぶ線分。
G=(V, E):グラフ
V:節点(node, 頂点)の集合
E:枝。辺。節点対e=(v1, v2)




/*木*/
連結有向グラフGが閉路をもたないときGを有向木という。
有向木において、根から他の任意の接点へ路が存在する。(根付き木)
★二分木:各ノードの子の数が2以下の木でかつ、左右の子を区別する場合の木。

木が(上から下へ)枝(u, v)を持つとき
根:1番上のノード。
親:uはvの親。
子:vはuの子。
長男:同じ親をもつ子の中で最も左の子。
 ⇒子の間の左右関係をもつ木:順序木
葉:子を持たないノード。
(uの)深さ:木のノードuにおいてuから根までの長さ。
(uの)高さ:木のノードuにおいてuから葉までの最長路の長さ。
木の高さ:根の高さ



/*木のなぞり*/
与えられた木Tのすべてのノードを組織だった方法で訪問し出力すること。

深さ優先探索:左から右へなぞっていく。
各節点を行き(1回)、途中(数回)、帰り(1回)の2回以上訪問する。
よっていつ節点を出力するかによって前順、中順、後順が考えられる。

P R
プロフィール
  • プロフィール画像
  • アイコン画像 ニックネーム:riesenrad
読者になる
2009年07月
« 前の月  |  次の月 »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
最新コメント
Yapme!一覧
読者になる