技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。

�V−４

以下の有向グラフで表された木構造と隣接行列において、ノード0から始める深さ優先探索を行うプログラムを考える。下線部の【ア】に入るプログラム片のうち、最も適切なものはどれか。



〔プログラム〕
mm=[[0,1,1,0,0,0,0,0,0],[0,0,0,1,1,0,0,0,0],
　　　[0,0,0,0,0,1,1,0,0],[0,0,0,0,0,0,0,0,0],
　　　[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,1],
　　　[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
　　　[0,0,0,0,0,0,0,0,0]]
def tsearch(l, d):
　for i, c in enumerate(l):
　　if (c==1):
　　　print('ノード:', i, '深さ:', d)
　　　　　　　　【ア】　　　　　

print('ノード: 0　深さ: 0')
tsearch(mm[0],1)

〔実行結果〕
ノード: 0　深さ: 0
ノード: 1　深さ: 1
ノード: 3　深さ: 2
ノード: 4　深さ: 2
ノード: 2　深さ: 1
ノード: 5　深さ: 2
ノード: 7　深さ: 3
ノード: 8　深さ: 3
ノード: 6　深さ: 2

---

正解

�B

---

解説

隣接行列は、頂点同士が辺でつながっているかどうかを表す行列である。
例えば、頂点0の隣接行列は、頂点1と頂点2につながっているので、
[0, 1, 1, 0, 0, 0, 0, 0, 0]と表せる。

ノード0の深さは0、ノード1および2の深さは1、ノード3, 4, 5, 6の深さは2、ノード7および8の深さは3である。

これらを深さ優先探索、すなわち各ノードを
0 ⇒ 1 ⇒ 3 ⇒ 4 ⇒ 2 ⇒ 5 ⇒ 7 ⇒ 8 ⇒ 6 の順に正しく出力できるようにプログラムを考える。


配列mmが定義され、次に
def tsearch(l, d)
　〜
　　【ア】 で
引数が l と d の関数trearch()を定義する。

プログラムは
print('ノード: 0　深さ: 0')で ノード: 0　深さ: 0 を出力した後、
tsearch(mm[0], 1) を実行し、tsearch()内で再帰的に呼び出される。

なお、enumerate()関数は for文でインデックスと要素を同時に取得する関数である。for i, c in enumerate(l): によって、引数のmmのリストを i と c に以下のように 取り出していく。
mm[0]のとき: (i, c) ⇒ (0, 0), (1, 1), (2, 1) ・・・ (9, 0)

これらを踏まえ、trearch(mm[0], 1) をトレースすると次のようになる。

trearch(mm[0], 1)
for 1回目
　(i, c) = (0, 0)
　c = 0だから print出力と【ア】は処理しない。
for 2回目
　(i, c) = (1, 1)
　c = 1だから、ノード: 1　深さ: 1 を出力

ここで、深さ優先探索なので次に探索するノードは1である。ノード1に対応する配列はmm[1] なので、i=1のままでtrearch() を呼び出す必要がある。また、ノード1に隣接するノード3や4の深さは2であるから、d=1に1を加えて、2として trearch() を呼び出す必要がある。
この時点で正解は�Cの tsearch( mm[i], d+1 ) であることが解る。

引き続きトレースすると以下の通りである。

　tsearch( mm[1], 1+1 )
　　for 1回目
　　　(i, c) = (0, 0)
　　for 2回目
　　　(i, c) = (1, 0)
　　　・・・
　　for 4回目
　　　(i, c) = (3, 1)
　　　ノード: 3　深さ: 2 を出力
　　　tsearch( mm[3], 2+1 )
　　　　for 1回目
　　　　　(i, c) = (0, 0)
　　　　for 2回目
　　　　　(i, c) = (1, 0)
　　　　　・・・
　　　　for 9回目
　　　　　(i, c) = (8, 0)
　　for 5回目
　　　(i, c) = (4, 1)
　　　ノード: 4　深さ: 2 を出力
　　　tsearch( mm[4], 2+1 )
　　　　for 1回目
　　　　　(i, c) = (0, 0)
　　　　for 2回目
　　　　　(i, c) = (1, 0)
　　　　　　・・・
　　　　for 9回目
　　　　　(i, c) = (8, 0)
　　for 6回目
　　　(i, c) = (5, 0)
　　　　・・・
　　for 9回目
　　　(i, c) = (8, 0)
for 3回目
　(i, c) = (2, 1)
　ノード: 2　深さ: 1 を出力
　tsearch( mm[2], 1+1 )
　　for 1回目
　　　(i, c) = (0, 0)
　　for 2回目
　　　(i, c) = (1, 0)
　　　・・・
　　for 6回目
　　　(i, c) = (5, 1)
　　　ノード: 5　深さ: 2 を出力
　　　tsearch( mm[5], 2+1 )
　　　　for 1回目
　　　　　(i, c) = (0, 0)
　　　　for 2回目
　　　　　(i, c) = (1, 0)
　　　　　　・・・
　　　　for 8回目
　　　　　(i, c) = (7, 0)
　　　　　ノード: 7　深さ: 3 を出力
　　　　　tsearch( mm[7], 3+1 )
　　　　　for 1回目
　　　　　　(i, c) = (0, 0)
　　　　　　　・・・
　　　　　for 9回目
　　　　　　(i, c) = (8, 0)
　　　　for 9回目
　　　　　(i, c) = (8, 0)
　　　　　ノード: 8　深さ: 3 を出力
　　　　　tsearch( mm[8], 3+1 )
　　　　　　for 1回目
　　　　　　　(i, c) = (0, 0)
　　　　　　　　・・・
　　　　　　for 9回目
　　　　　　　(i, c) = (8, 0)
　　for 7回目
　　　(i, c) = (6, 1)
　　　ノード: 6　深さ: 2 を出力
　　　tsearch( mm[6], 2+1 )
　　　　for 1回目
　　　　　(i, c) = (0, 0)
　　　　　　・・・
　　　　for 9回目
　　　　　(i, c) = (8, 0)
　　for 8回目
　　　(i, c) = (7, 0)
　　for 9回目
　　　(i, c) = (8, 0)
for 4回目
　(i, c) = (3, 0)
for 5回目
　(i, c) = (4, 0)
　　　・・・
for 9回目
　(i, c) = (8, 0)

�V−３

目次

�V−５

---