アルゴリズムとプログラミング
基本情報技術者試験｜有向グラフを次の辺リストで与える（u → v は u から v への辺）。 1→2, 1→3, 2→4,…
有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3, 2→4, 5→1
次の手続 reachCount は、始点 s から有向辺をたどって到達できるノードの総数（s 自身を含む）を返す。スタックを用いた深さ優先で探索する。reachCount(1) を実行したとき、戻り値はどれか。
○整数型: reachCount(整数型: s)
stack ← 空のスタック
visited[s] ← true
push(s)
整数型: cnt ← 1
while (stack が空でない)
整数型: u ← pop()
整数型: v
for (v を 1 から 5 まで 1 ずつ増やす)
if (辺 u→v が存在 かつ visited[v] が false)
visited[v] ← true
cnt ← cnt + 1
push(v)
endif
endfor
endwhile
return cntア到達 4 個
イ全 5 個
ウ始点のみ 1 個
エ2 個
正解
ア．到達 4 個
1 から有向辺をたどると 2,3 へ、さらに 2 から 4 へ到達する。到達集合は {1,2,3,4} の 4 個であり、5 は 1 へ向かう辺しか持たず到達できないため、cnt=4 となり アが正しい。
?選択肢ごとの解説
ア ○1 から有向辺をたどると 2,3 へ、さらに 2 から 4 へ到達する。到達集合は {1,2,3,4} の 4 個であり、5 は 1 へ向かう辺しか持たず到達できないため、cnt=4 となり アが正しい。
イ ×全ノード数 5 をそのまま答えた、有向辺の向きを無視して 5→1 を逆向きにたどれると誤認した誤りである。
ウ ×始点 1 だけを数えて隣接ノードへの探索を行わなかった、ループ未実行の誤りである。
エ ×1 の直接の隣接 2,3 のうち 1 つ分しか進めず 2 個とした、間接到達 4 と分岐を取りこぼした誤りである。
アルゴリズムとプログラミングの他の問題
6 個のノード 1〜6 から成る無向グラフを隣接行列 M で表す（M[i][j]=1 で辺あり、添字は 1…5 個のノード 1〜5 から成る無向グラフを隣接行列 M で表す（M[i][j]=1 で辺あり、添字は 1…無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。
1—2, 1—3, 2—4, 3—4,…無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。
1—2, 2—3, 4—5
次の手続…有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→3, 2→3, 4→3, 2→5, 4→5…6 個のノード（番号 1〜6）からなる有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2,…4 個のノード 1〜4 から成る有向グラフを隣接行列 M で表す。M[i][j]=1 ならノード i から j…頂点数nのグラフを隣接行列で表現したとき、必要な記憶領域の大きさのオーダはどれか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0149