解説 6月21日B

今日の学習項目です。


スタックと縦型探索

6月14日Bの講義で、横型探索を学びました。 またそのためにキューというデータ構造が用いられました。 ここでは、「縦型探索」(depth-rist search)を学びます。 木の横型探索では深さ順に頂点が探索されましたが、縦型探索はまず根の頂点、 次に根の最初の(左の)子を根とする部分木、次にその子の兄弟を根とする部分木、... というように探索されます。 木のなぞり方は、根からまず葉に向かって深く探索し、そこから行きつ戻りつしながらほかの頂点を探索する、というようにおこなわれます。

課題1-1

この課題では、6月21日Aの講義で定義したクラスStackをここで使います。 また、二進木の頂点を表すためのクラスNodeをRubyで次のように表すとします:
   class Node   # クラスの定義の始まり
        def initialize(l, x=nil, y=nil)  # インスタンスを作るためのメソッド
            @label = l      # label(頂点のラベル)を表す「要素」を定義
            @left = x       # left son(左の子)を表す「要素」を定義
            @right = y      # right son(右の子)を表す「要素」を定義
        end  # of def
        attr_accessor :label, :left, :right   # インスタンス変数へのアクセスを可能にする
       def depthFirst  # 縦型探索
           nodes = [ ]    # 答えを返すための配列
           agenda = Stack.new  # スタックを用意
           agenda.push(self)       # スタックに自分自身をいれる
           while (! agenda.empty)   # スタックに要素がある限り
             x = agenda.popup  # スタックから要素を取り出す
             nodes = nodes + [x.label]   # 要素のラベルを記録
             agenda.push(x.right) if x.right != nil  # 右の子頂点をスタックにいれる
             agenda.push(x.left) if x.left != nil   # 左の子頂点をスタックにいれる
          end   # while
         return nodes   # 頂点のラベルの配列を返す
       end  # def of breadthFirst
   end  # of Class
これはVertexクラスと異なり、親頂点や兄弟頂点へのポインタは持たず、 それぞれの頂点の左の子頂点と右の子頂点へのポインタだけをもつ定義となっています。

6月7日Bの講義課題1-2で書いた二進木を使うことにします。 この根頂点が変数rの値となっているとします。 r.depthFirstの結果はどのようなものでしょうか、予想して書きなさい。 また、プログラムを実行して、その結果と比較しなさい。

課題1-2

二進木の頂点を表すためのクラスNodeをRubyで次のように表すとします。大きな変更点はdepthFirstメソッドの定義です:

   class Node   # クラスの定義の始まり
        def initialize(l, x=nil, y=nil)  # インスタンスを作るためのメソッド
            @label = l      # label(頂点のラベル)を表す「要素」を定義
            @left = x       # left son(左の子)を表す「要素」を定義
            @right = y      # right son(右の子)を表す「要素」を定義
        end  # of def
        attr_accessor :label, :left, :right   # インスタンス変数へのアクセスを可能にする
       def depthFirst  # 縦型探索
           nodes = [@label]
           if (@left != nil)
              nodes = nodes + @left.depthFirst()
           end # if
           if (@right != nil)
              nodes = nodes + @right.depthFirst()
           end # if
         return nodes   # 頂点のラベルの配列を返す
       end  # def of breadthFirst
   end  # of Class
課題1-1と同じ二進木を与えて、結果を比較せよ。 また、これは今まで学んだ二進木のなぞりの方法(先行順、中間順、後行順)の中でどれに近い方法と考えられるか、答えよ。

課題1-3

課題1-1では二進木に対して縦型探索を行いましたが、 この課題では一般の木に対して縦型探索を行ってみましょう。そのために 6月14日Bの講義で扱った「木の頂点を表すためのクラスVertex」 を用います。以下に再掲します:

   class Vertex   # クラスの定義の始まり
        def initialize(l, p = nil, b = nil, f = nil)  # インスタンスを作るためのメソッド
            @label = l      # label(頂点のラベル)を表す「要素」を定義
            @parent = p        # parent(親)を表す「要素」を定義
            @nextBrother = b   # nextBrother(次の兄弟)を表す「要素」を定義
            @firstChild = f    # firstChild(第1子)を表す「要素」を定義
        end  # of def
        attr_accessor :label,:parent, :firstChild, :nextBrother   # インスタンス変数へのアクセスを可能にする
   end  # of Class
縦型探索を行う depthFirst関数をこのクラスのメソッドとして書きなさい。 また、適当な大きさの木をこのクラスを用いて表現し、その根頂点に対してdepthFirstを実行した時に、 縦型探索がちゃんと行われることを確かめなさい。
[ヒント(1)]
この問題を解くには、「(ある頂点にたいする)子頂点すべてからなる配列」を求めるメソッドを作っておくとよい。6月14日Bの課題1-2のヒント(1)を参照のこと。
[ヒント(2)]
「子頂点すべてからなる配列」を求めるメソッドができているとします。 まず根頂点(のラベル)を出力します(もしくは、出力用の配列に入れます)。 そして、その配列の要素(つまり子頂点それぞれ)に対して縦型探索を行います。 これにより「木の縦型探索」が実現できます。出力用の配列にいれた場合は、 その配列をreturnするのを忘れないようにすること。

「アルゴリズムとデータ構造」のホームに戻る