アルゴリズムとプログラミング
基本情報技術者試験｜無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。 1—2, 2—3, 4—5…
無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。
1—2, 2—3, 4—5
次の手続 isConnected は、深さ優先で始点 a から探索し、終点 b に到達できれば true、できなければ false を返す。isConnected(1, 3) を実行したとき、戻り値はどれか。
○論理型: isConnected(整数型: a, 整数型: b)
stack ← 空のスタック
visited[a] ← true
push(a)
while (stack が空でない)
整数型: u ← pop()
if (u が b と等しい)
return true
endif
整数型: v
for (v を 1 から 5 まで 1 ずつ増やす)
if (辺 u—v が存在 かつ visited[v] が false)
visited[v] ← true
push(v)
endif
endfor
endwhile
return falseアtrue（連結している）
イfalse（連結していない）
ウ探索は終了しない
エ実行時エラーで停止
正解
ア．true（連結している）
ノード 1 と 3 は 1—2、2—3 を介して同じ連結成分に属する。深さ優先で 1→2→3 とたどると b=3 に到達し true を返すため アが正しい。
?選択肢ごとの解説
ア ○ノード 1 と 3 は 1—2、2—3 を介して同じ連結成分に属する。深さ優先で 1→2→3 とたどると b=3 に到達し true を返すため アが正しい。
イ ×4—5 が別成分であることに引きずられ 1 と 3 も非連結と誤認した誤りで、実際は 1—2—3 でつながっている。
ウ ×visited による訪問管理で各ノードは 1 回しか push されないため探索は必ず停止する。無限ループとした誤りである。
エ ×添字や辺は正しく定義されており、実行時エラーは発生しない。例外発生とした誤りである。
アルゴリズムとプログラミングの他の問題
有向グラフを次の辺リストで与える（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のグラフを隣接行列で表現したとき、必要な記憶領域の大きさのオーダはどれか。5 個のノード 1〜5 から成る無向グラフを、隣接行列 M で表す。M[i][j] が 1 ならノード i と j…有向グラフを次の辺リストで与える（u → v は u から v への辺を表す）。
1→2, 1→4, 2→3, 2→5,…有向グラフを次の辺リストで与える（u → v は u から v への辺を表す）。
1→2, 1→4, 2→3, 4→5,…閉路のない有向グラフ（DAG）を次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3,…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0153