二分木の深さ優先探索と幅優先探索｜新しい擬似言語で学ぶ科目 B アルゴリズムとプログラミング入門

矢沢久雄
2023-11-16 更新

基本情報技術者試験は、2023年4月から新制度で実施されています。

この連載では、新制度の擬似言語（旧制度の擬似言語とは、表記方法に違いがあります）を使って、試験のシラバス（情報処理技術者試験における知識・技能の細目）に示されている代表的なアルゴリズムとデータ構造を、プログラミング入門者向けにやさしく解説します。
受験対策としてだけでなく、アルゴリズムとプログラミングの基礎知識を習得するために、ぜひお読みください。

今回は、「二分木」というデータ構造と「深さ優先探索」「幅優先探索」というアルゴリズムを取り上げます。

1 二分木とは？深さ優先探索、幅優先探索とは？
2 深さ優先探索のプログラムを見てみよう
- 2.1 問９
3 VBScriptでプログラムを実行してみよう

二分木とは？深さ優先探索、幅優先探索とは？

「二分木」は、 1つの要素（データ）が2つの要素につながることを繰り返したデータ構造です。二分木の形式には、探索を効率的に行える「二分探索木」や、整列を効率的に行える「ヒープ」などがありますが、この記事では、二分木のすべての要素をたどるアルゴリズムをテーマにします。

単純なデータ構造である1次元配列であれば、すべての要素をたどるのは、とても簡単です。1次元配列の先頭から末尾まで、要素番号の順に要素をたどればよいからです。
それに対して、二分木のすべての要素をたどるのは、やや困難です。様々なたどり方が考えられるからです。もしも、たどり方の手順に不備があると、いくつかの要素をたどれない場合もあります。

二分木のすべての要素を確実にたどるアルゴリズムには、
「深さ優先探索（DFS＝Depth First Search）」と「幅優先探索（BFS＝Breadth First Search）」があります。

深さ優先探索の例を図1に、幅優先探索の例を図2に示します。

1次元配列を図示するときは、要素を四角形で示しますが、二分木を図示するときは、慣例として要素を円で示します。円と円をつなぐ線で、要素のつながりを示します。
ここでは、A～Gが要素です。1～7は、要素をたどる順序です。

二分木の根元にある要素を「根」と呼びます。
深さ優先探索では、根（A）から始めて、どんどん先の要素に（深い向きに）たどっていきます。左右の2つの要素がある場合は、先に左側をたどり、左側が末端になったら右側をたどります。
図1の場合は、左側にA→B→Dとたどって末端になり、右側のEにたどって末端になり、右側のCから左側のFにたどって末端になり、右側のGにたどります。

幅優先探索では、根（A）から始めて、直接つながっている要素を左から右の横に（幅の向きに）たどっていきます。
図2の場合は、Aに直接つながっているA→B→Cとたどり、Bに直接つながっているD→Eとたどり、Cに直接つながっているF→Gをたどります。

深さ優先探索のプログラムを見てみよう

2022年12月に公開された科目Bサンプル問題セットの問9に、深さ優先探索を行うプログラムが示されています。
深さ優先探索を行うには、以下の2つの方法があります。
・再帰呼び出し（関数や手続の処理の中で、同じ関数や手続を呼び出して、繰り返しを実現するプログラミング技法）を使う
・スタック（後入れ先出し形式のバッファ）を使う

この問題では、再帰呼び出しを使っています。
深さ優先探索の具体例として、プログラムの内容を見てみましょう。以下に問題を示します。

問９

次の記述中のに入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。

手続 order は，図の2分木の，引数で指定した節を根とする部分木をたどりながら，全ての節番号を出力する。大域の配列 tree が図の2分木を表している。
配列 tree の要素は，対応する節の子の節番号を，左の子，右の子の順に格納した配列である。例えば，配列 tree の要素番号1の要素は，節番号1の子の節番号から成る配列であり，左の子の節番号2，右の子の節番号3を配列｛2，3｝として格納する。
手続 order を order(1)として呼び出すと，の順に出力される。

プログラム

    
大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9},{10, 11}, {12, 13}, {14}, {}, {}, {}, {}, {}, {}, {}} // {}は要素数0の配列	

○order(整数型: n)
    if (tree[n]の要素数 が 2 と等しい) 
        order(tree[n][1]) 
        nを出力
        order(tree[n][2]) 
    elseif (tree[n]の要素数 が 1 と等しい) 
        order(tree[n][1]) 
        nを出力 
    else 
        nを出力 
    endif

解答群
　ア 1，2，3，4，5，6，7，8，9，10，11，12，13，14
　イ 1，2，4，8，9，5，10，11，3，6，12，13，7，14
　ウ 8，4，9，2，10，5，11，1，12，6，13，3，14，7
　エ 8，9，4，10，11，5，2，12，13，6，14，7，3，1

問題に示されたプログラムは、大域の整数型の配列の配列（以下、2次元配列と呼びます）treeと、引数nで指定された要素を基点として深さ優先探索を行う手続orderから構成されています。
手続orderをorder(1)として呼び出すと、どのような順で要素が出力されるかを答えます。
配列の要素番号は1から始まるとしているので、order(1)は、二分木の根からすべての要素をたどります。この問題では、2次元配列の要素を「要素」と呼び、二分木の要素を「節」と呼んでいますが、これ以降の説明では、どちらも「要素」と呼びます。

問題の図に示された二分木と2次元配列treeの要素を見比べて、プログラムで二分木がどのように表現されているのかを理解してください（二分木の表現方法は、いろいろあります。このプログラムの表現方法は、その一例です）。
図の注記1から、2次元配列treeの要素番号が、図の二分木の円の中に示された数字に対応していることがわかります。2次元配列treeの個々の要素の1番目の要素の値（2次元配列は、要素が1次元配列であり、その１次元配列の中に要素の値があります）が、左側につながっている要素の要素番号を示し、2番目の要素が、右側につながっている要素の要素番号を示しています。

たとえば、2次元配列treeの1番目の要素は {2, 3} です。
これは、この要素が①に対応し、①の左側が②であり、①の右側が③であることを示しています。
｛7｝のように、要素が1つだけの場合は、図の注記2から、左側の要素を示している（左側だけに要素がある）ことがわかります。要素がない { } は、その先につながる要素がないことを示しています。

手続orderは、再帰呼び出しで、深さ優先探索を行っています。
ここでは、すべての要素をたどるだけでなく、要素の値の出力も行っています（画面への出力なら表示されます）。手続orderの処理内容は、if文で3つに分けられています。

「tree[n]の要素が2と等しい」という条件が真なら、要素nの先に2つの要素がつながっています。
この場合には、左側の要素を意味するtree[n][1]を引数に指定して、手続orderを再帰呼び出しします。
これによって、左側にたどることになります。
左側がたどり終わったら、「nを出力」してから、右側の要素を意味するtree[n][2]を引数に指定して手続orderを再帰呼び出しします。これによって、右側にたどることになります。

「tree[n]の要素が1と等しい」という条件が真なら、要素nの先に1つの要素（左側の要素）だけがつながっています。
この場合には、左側の要素を意味するtree[n][1]を引数に指定して、手続orderを再帰呼び出しします。これによって、左側にたどることになります。
左側が終わったら「nを出力」します。右側には要素がないのですから、右側にはたどりません。

上記の2つの条件が真でないなら、要素nの先に要素がない、つまり、要素nが末端ということです。この場合には、「nを出力」するだけです。

手続orderの処理内容がわかったら、図に示された二分木の要素が、どういう順番で出力されるかがわかるでしょう。
問題の解答群を見ると、最初から3番目までに出力される要素がわかれば、答えを選べます。
まず、根の要素①から左側にたどって、末端の要素⑧が出力されます。
次に、⑧の上にある④が出力されてから、④の右側にたどって、
末端の⑨が出力されます。

ここまでの出力は、⑧、④、⑨であり、選択肢ウが正解です。

正解：ウ

VBScriptでプログラムを実行してみよう

擬似言語で示されたプログラムを見ただけでは、再帰呼び出しで深さ優先探索を実現するイメージがつかめない、という人もいらっしゃると思いますので、先ほどの問題に示されたプログラムと同様の機能のプログラムを、VBScript（Visual Basic Scripting Edition）で作成して実行してみましょう。
VBScriptは、Windowsパソコンであれば、何もツールをインストールせずに、すぐに実行できるプログラミング言語です。

リスト1に示したプログラムを、dfs.vbsというファイル名で任意のディレクトリに保存してください。ここでは、C:\testというディレクトリに保存しています。
Windowsのコマンドプロンプトを起動して、カレントディレクトリをC:\testに移動したら、「cscript dfs.vbs」と入力して「Enter」キーを押せば、プログラムを実行できます。
プログラムの実行結果の例を図3に示します。先ほどの問題の解答群の選択肢ウと同じ出力が得られました。

リスト1　VBScriptで作成した深さ優先探索のプログラム

‘ 大域の整数型の配列の配列
tree = Array(Array(2, 3), Array(4, 5), Array(6, 7), Array(8, 9), _
Array(10, 11), Array(12, 13), Array(14), Array(), Array(), Array(), _
Array(), Array(), Array(), Array()) ‘ Array()は要素数0の配列

‘ 手続orderの定義
Sub order(n)
‘ 試験問題の配列の要素番号は1から始まり
‘ VBScriptの配列の要素番号は0から始まるので
‘ n – 1を代入したidxでVBScriptの配列を取り扱う
idx = n – 1

‘ tree(n)の要素数が2の場合
If UBound(tree(idx)) + 1 = 2 Then
order(tree(idx)(0))
WScript.StdOut.Write(n & “, “)
order(tree(idx)(1))
‘ tree(n)の要素数が1の場合
ElseIf UBound(tree(idx)) + 1 = 1 Then
order(tree(idx)(0))
WScript.StdOut.Write(n & “, “)
‘ tree(n)の要素数が0の場合
Else
WScript.StdOut.Write(n & “, “)
End If
End Sub

‘ 手続orderをorder(1)として呼び出す
order(1)
‘ 最後に改行する
WScript.StdOut.WriteLine()

リスト1のポイントとなる部分（問題に示された擬似言語のプログラムと表現が大きく異なる部分）を説明しましょう。
VBScriptでは、Array関数の引数に要素をカンマで区切って指定して、配列を作成します。
ここでは、2次元配列なので、Array関数の引数でArray関数を使って、配列の配列を作成しています。引数がないArray関数は、要素がない配列を作成します。VBScriptでは、長い命令を途中で改行するときに、行の末尾にアンダースコア（ _ ）を置きます。

問題のプログラムでは、要素番号が1から始まりますが、VBScriptでは要素番号が0から始まるので、手続orderの中でidx = n – 1という処理を行い、変数idxにVBScript用の要素番号を得ています。UBound関数は、引数に指定された配列の末尾の要素の要素番号を返します。これに1を足すことで、要素数が得られます（VBScriptでは要素番号が0から始まるからです）。
擬似言語では、配列の要素番号を [ ] で囲みますが、VBScriptでは ( ) で囲みます。WScript.StdOut.Write(n & “, “)は、nの値とカンマを表示します（表示の末尾で改行しません）。WScript.StdOut.WriteLine()は、改行だけを行います。
その他の部分は、問題に示された擬似言語のプログラムと同様です。

☆　　　☆　　　☆

今回は、「二分木」というデータ構造と「深さ優先探索」「幅優先探索」というアルゴリズムを取り上げました。

次回も、シラバスに示されたアルゴリズムとデータ構造を解説します。
それでは、またお会いしましょう！