基本情報技術者試験「グラフ」の問題
閉路のない有向グラフ（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 となるため エが正しい。
✎くわしく
DAG の経路数は『各後続ノードの経路数の総和』という再帰式で求まる。f(t)=1 を基底とし、終点に近いノードから前へ加算する動的計画法の考え方が核心である。
✓本番での押さえどころ
試験のコツ
終点から逆向きに各ノードの『6 への経路数』をメモし、辺をたどって合算する。
覚え方
『経路数＝行き先の経路数の足し算、終点は 1』と覚える。
よくある誤り
2 や 3 から 6 へ直接行く辺（2→6, 3→6）と 4・5 経由を二重に数えたり、逆に経由経路を落とすミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0148