基本情報技術者試験の勉強をしております。 以下の問題はどうしてその処理をしているのか、解説を見ても全く分かりません。 …

Question

基本情報技術者試験の勉強をしております。
以下の問題はどうしてその処理をしているのか、解説を見ても全く分かりません。

特に分からないのが、

visit(node)⇐1

fornodeの値を出力
for(jを1からnまで1ずつ増やす)
if(martrix(node,j)=1 and visit(j)=0)
graphSearch(j)

endif
endfor

の部分です。

nodeの値を出力
→1を出力する

for(jを1からnまで1ずつ増やす)
→jを1から6まで1ずつ増やす

if(martrix(node,j)=1 and visit(j)=0)
→martrix(1,1)=1 and visit(1)=0

martrix(1,1)は0です。
配列visit(1)も0です。

なのでgraphSearch(j)の処理はせずに
jを2にします。
→martrix(1,2)=1 and visit(2)=0
martrix(1,2)は1、配列visit(2)は0で条件を満たすため、graphSearch(2)を出力。

jが3になった時も
martrix(1,3)=1 and visit(3)=0のため、graphSearch(3)を出力。

となると理解してます。

「for(jを1からnまで1ずつ増やす)」とプログラムにあるので、6まで行ったら繰り返し処理は終わる(つまりmartrix(1,6)まで行ったら終わり)認識なのですが、どうしてnode2とnode3に紐づいている、4.5.6が出力されるのか分かりません。

私がアルゴリズムを理解しきれてないのだと思うのですが、お知恵を貸していただければ幸いです。

Answer 1

再帰(Recursive)というのは、関数が関数自身を呼び出すことです。

詳しくは、問題文をトレースしましたので確かめてください。

GS(1)
visit[1]←1
node: 1
for(j, 1→6, 1)
if(matrix[1, 1]=1 and visit[1]=0)☓
if(matrix[1, 2]=1 and visit[2]=0)◯
GS(2)
visit[2]←1
node: 1
for(j, 1→6, 1)
if(matrix[2, 1]=1 and visit[1]=0)☓
if(matrix[2, 2]=1 and visit[2]=0)☓
if(matrix[2, 3]=1 and visit[3]=0)☓
if(matrix[2, 4]=1 and visit[4]=0)◯
GS(4)
visit[4]←1
node: 1
for(j, 1→6, 1)
if(matrix[4, 1]=1 and visit[1]=0)☓
if(matrix[4, 2]=1 and visit[2]=0)☓
if(matrix[4, 3]=1 and visit[3]=0)☓
if(matrix[4, 4]=1 and visit[4]=0)☓
if(matrix[4, 5]=1 and visit[5]=0)☓
if(matrix[4, 6]=1 and visit[6]=0)☓
if(matrix[2, 5]=1 and visit[5]=0)◯
GS(5)
visit[5]←1
node: 1
for(j, 1→6, 1)
if(matrix[5, 1]=1 and visit[1]=0)☓
if(matrix[5, 2]=1 and visit[2]=0)☓
if(matrix[5, 3]=1 and visit[3]=0)☓
if(matrix[5, 4]=1 and visit[4]=0)☓
if(matrix[5, 5]=1 and visit[5]=0)☓
if(matrix[5, 6]=1 and visit[6]=0)☓
if(matrix[2, 6]=1 and visit[5]=0)◯
GS(5)
visit[5]←1
node: 1
for(j, 1→6, 1)

トレース量が地獄なので、ここで止めておきますが、
visit[1]←1
visit[2]←1
visit[4]←1
visit[5]←1

と続きますので、イが正解です。

Answer 2

隣接行列は、添付図のグラフを表しています。

このグラフの繋がりをノード①をスタートに繋がっているノード番号を抽出するというのが、このグラフ探索の手順の意図です。

①からスタートして、若番の番号から辿り、下まで辿ったら、戻って、別の枝を辿るというアルゴリズムになっています。

どのぐらい深く辿るか分からないので、探索手順の再帰呼び出しをしています。つまり、①から②に行くと、②を初期値だと思って再度探索を始めるわけです。
この時、visitが一度訪れたノード番号を覚えているので、一度も訪れたことがないノードだけを辿ることで、赤矢印のような探索となるのです。

Answer 3

例えばこれ。
https://gimo.jp/glossary/details/recursion.html#:~:text=%E5%86%8D%E5%B8%B0%E5%87%A6%E7%90%86%E3%81%A8%E3%81%AF%E3%80%81%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0,%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%81%A8%E5%91%BC%E3%81%B3%E3%81%BE%E3%81%99%E3%80%82

Answer 4

＞「for(jを1からnまで1ずつ増やす)」とプログラムにあるので、6まで行ったら繰り返し処理は終わる

C言語の教科書を購入して再帰の箇所を読みます。