アルゴリズムとプログラミング
基本情報技術者試験｜閉路のない有向グラフ（DAG）を次の辺リストで与える（u → v は u から v への辺）。 1→2,…
閉路のない有向グラフ（DAG）を次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3, 2→4, 2→5, 2→6, 3→4, 3→5, 3→6, 4→6, 5→6
次の再帰手続 countPaths は、ノード s からノード t へ至る相異なる有向経路の総数を返す。countPaths(1, 6) を実行したとき、戻り値はどれか。
○整数型: countPaths(整数型: s, 整数型: t)
if (s が t と等しい)
return 1
endif
整数型: total ← 0
整数型: v
for (v を 1 から 6 まで 1 ずつ増やす)
if (辺 s→v が存在)
total ← total + countPaths(v, t)
endif
endfor
return totalア3 通り
イ8 通り（二重計上）
ウ2 通り
エ全 6 通り
正解
エ．全 6 通り
DAG の経路数は後続ノードの経路数の総和で求まる。f(6)=1、f(4)=f(6)=1、f(5)=f(6)=1、f(2)=f(4)+f(5)+f(6)=1+1+1=3、f(3)=同様に 3、f(1)=f(2)+f(3)=3+3=6 となるため エが正しい。
?選択肢ごとの解説
ア ×1 の直接分岐 1→2,1→3 と末端だけを数えて 3 通りとした、中間分岐を取りこぼした過少カウントである。
イ ×存在しない辺や同一経路を二重計上して 1 つ多く 8 通りとした過大カウントである。
ウ ×1→2→6 と 1→3→6 の直接経路 2 本だけを数え、4 や 5 を経由する経路を見落とした誤りである。
エ ○DAG の経路数は後続ノードの経路数の総和で求まる。f(6)=1、f(4)=f(6)=1、f(5)=f(6)=1、f(2)=f(4)+f(5)+f(6)=1+1+1=3、f(3)=同様に 3、f(1)=f(2)+f(3)=3+3=6 となるため エが正しい。
アルゴリズムとプログラミングの他の問題
有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3, 2→4, 5→1
次の手続…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…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0148