基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

大滝本の応用問題で躓いてます。
再帰処理が分かりません。解説を見ても再帰処理の項目を見ても分からず止まってしまってます。
回答は「1.2.4.5.3.6」になります。

以下、問題です。

大域  2次元配列martrix (0.1.1.0.0.0)

   (1.0.0.1.1.0)

   (1.0.0.0.0.0)

   (0.1.0.0.0.0)

   (0.1.0.0.0.0)

   (0.0.1.0.0.0)
大域  n←6
大域  配列visit←(0.0.0.0.0.0)

graphSearch(整数型node)
整数型 j
visit(node)←1
nodeの値を出力

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

endif
endfor

私は以下のように考えました。
ーーーーーーーー
visit(node)←1
nodeの値を出力
?visit(1.0.0.0.0.0)
node「1」を出力

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

?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が出力されるのか分かりません。

根本の理解が間違ってるのでしょうか？
ここだけ全く理解できず途方に暮れてます。

よろしくお願いします。

この投稿は投稿者により削除されました。(2024.02.09 08:59)

この投稿は投稿者により削除されました。(2024.02.09 11:53)

■質問のこと
">どうしてnode2とnode3に紐づいている、4.5.6が出力されるのか分かりません。"

下の２つの時にもそれぞれ値の出力だけでなく
">martrix(1,2)は1、配列visit(2)は0で条件を満たすため、graphSearch(2)を出力。"
・ノード２の時の１から６までのループ
">martrix(1,3)=1 and visit(3)=0のため、graphSearch(3)を出力。"
・ノード３の時の１から６までのループ
を実施したからになります。

■処理の動きについて
再帰関数（別関数も）を途中で呼び出すと、現在の実行行で一旦処理を停止し呼び出された関数を開始・終了と同時に停止していた処理を続行させます。
○関数１
＿処理A
＿関数２呼び出し
＿処理B

○関数２
＿関数３呼び出し
＿処理C

○関数３
＿処理D

この時○関数１から処理を開始した場合の処理順は
処理A→処理D→処理C→処理B
となります。
※ループの途中であっても、ループという処理が一旦停止し同じように呼び出された関数が開始されます。

処理を追っていく上で局所変数（ローカル）は関数毎の扱いで他に影響を及ぼさないですが、大域変数は常に値が変化していくので注意が必要です。

■グラフ化してみると
書籍を持っていないのでどのように解説されているかわかりませんが、隣接行列はノード（頂点）間のエッジ（辺）を表しています。
※私は数字が得意ではないので間違ってたらすみません。

大域  2次元配列martrix
(0.1.1.0.0.0)
(1.0.0.1.1.0)
(1.0.0.0.0.0)
(0.1.0.0.0.0)
(0.1.0.0.0.0)
(0.0.1.0.0.0)

この数字をノードにしてみると下記のようなグラフで書き出せます。
※ノード６から３は一方向につながっている
６→３ー１ー２ー４
＿＿＿＿＿＿｜
＿＿＿＿＿＿５

プログラムの意図はよくわかりませんが、あるノードを指定したらそこから移動できる（visit訪れていない）場所へ、小さい順に移動して都度ノードの数字を出しているようです。

>スレ主さん
この問題は再帰があると考えた方があり、
またこの問題(行列とはいえど木構造です)は、
深さ優先と幅優先という考え方があるとまずは知ってください。
ちょっと特殊な問題なのでこんな考え方があるんだと知っていただけると幸いです。

1がある場所は
行列
(1.2)（1.3）（2.3）（2.4）（2.5）（3.6）なので1から出発して2という風にします

            1
      2              3
  4      5              6

こんな風な木構造を考えればはOKです

スレ主さんの考え方は幅優先という考え方ですそれだと答えがアになってしまいます
この問題はP163にも書いてあるように深さ優先なので、詳しくはP32の二分木の走査を読んでください。

まずノードが1の時に
visit(node)←1
nodeの値を出力  （1）
2、3が出された後
先行順で
4→(2)→5→（1）→3→6となります
なので答えは
1→2→4→5→3→6
この問題が出来れば、サンプル問題の問9が出来るはずです。
頑張りましょう

もし幅探索なら1，2，3，4，5，6になります
説明は難しいですが、似たような問題は出てますので考え方を身につけましょう

> まきさん(No.5) 
> 
> 1がある場所は
> 行列 (1.2)（1.3）（2.3）（2.4）（2.5）（3.6）

私はその参考書を持っていないので転記間違いかどうかは分かりません。
ただ，No.1 が正しいのであれば，最後は (3,6) ではなく (6,3) です。
(6,3) で正しいのであれば，
この行列が表しているのは木ではなく有向グラフです。

皆様色々ありがとうございます。

配列に転記ミスがありました。
大変申し訳ございません。

(0.1.1.0.0.0)
(1.0.0.1.1.0)
(1.0.0.0.0.1)←6番目は1になります。
(0.1.0.0.0.0)
(0.1.0.0.0.0)
(0.0.1.0.0.0)

なのでまき様が言っていることは正しいです。

>>電タックさん

ありがとうございます。
「ノード２の時の１から６までのループ」を「ノード３の時の１から６までのループ」
を行っている、ということで理解しました。

つまりはgraphSearch(2)とgraphSearch(3)が出力されるが、
先にgraphSearch(2)のnodeで処理を行う。
そうするとgraphSearch(4)とgraphSearch(5)が出力される。
この時点で1→2→4→5となる。
左側はそれ以上節が無いため、元の場所に戻り、graphSearch(3)の処理を行う。
すると

1→2→4→5→3→6

と出力される。ということですね。

>>※ループの途中であっても、ループという処理が一旦停止し同じように呼び出された関数が開始されます。
→この部分大変重要だということが理解できました。
処理が書いてあるので、ループ処理を実施しているのかと思っていたのですが、
呼び出された関数が開始されて、その関数の処理が終わった後に再び元の処理に戻る認識です。

懇切丁寧に解説いただきありがとうございました。

>>まきさん

ありがとうございます。
私のやり方は深さ優先ではなくて幅優先の解き方だったのですね…
P32の走査も確認しました。
また解説にも幅優先の場合の解き方が記載があったので、そちら現在熟読しております。
サンプル問題もちょろっと見てみたのですが、これは同じ深さ探索でも少し解き方が違うようで、
「(n)(1)」の表記が何を表しているのか初見では分かりませんでした。
二分探索木は勝手に苦手意識を持ってしまっているので、Youtubeやテキストを使ってしっかり理解するようにいたします。

＞jjon-comさん
私書籍もっているので、グラフ探索の問題ですと書かれており
P162にこれをグラフを表すと2分木になりますと書かれているですが・・・
これ有向グラフなんですか？

>>まきさん
わたしがそもそも記載した二次元配列の(3,6)の項目を「0」としてしまったため、このようなことになっているのだと思います。
本書は(3,6)は「1」なので探索木なんだと思います。

もし本当に本書の(3,6)が「0」なら有向グラフと呼ばれるものになるのかと推察してます。

行列が No.1 のとおりなら（No.7 の状態でないのなら）
それは木ではないです，と私は発言しました。

> 私書籍もっているので（略）
> P162に（略）2分木になりますと書かれている

とおっしゃられても，私は書籍を持っていないので
それを 私と まきさん との共通了解事項にはできないです。

まきさん は手元の書籍を見て，その記載どおり，
> 行列 (1.2)（1.3）（2.3）（2.4）（2.5）（3.6）
と書いたのかもしれませんが，
私には まきさんの No.5 の文は
No.1に登場する (0.0.1.0.0.0) を (3,6) と間違って解釈したように読める。
ですから No.6 を書きました。

ということで。
No.7 の修正後の行列が 木を表していることは 私も理解しています。

>jjon-comさん
承知致しました。