基本情報技術者試験「グラフ」の問題
有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→3, 2→3, 4→3, 2→5, 4→5
各ノードの入次数（そのノードへ入ってくる辺の本数）を数え、入次数が最大のノードの番号を求める。最大が同数のときは番号の小さいノードを選ぶ。次の擬似言語を実行したとき返り値 best はどれか。
○関数: maxInDegree(): 整数型
整数型の配列: indeg ← {0, 0, 0, 0, 0}
各辺 u→v について
indeg[v] ← indeg[v] + 1
整数型: i, best ← 1
for (i を 2 から 5 まで 1 ずつ増やす)
if (indeg[i] > indeg[best])
best ← i
endif
endfor
return bestアノード 5（入次数 2）
イノード 3（入次数 3）
ウノード 2（入次数 0）
エノード 4
正解
イ．ノード 3（入次数 3）
辺の終点 v を数えると、ノード3へは 1→3, 2→3, 4→3 の 3 本、ノード5へは 2→5, 4→5 の 2 本、他は 0 本である。indeg={0,0,3,0,2} の最大はノード3（3本）なので best=3、すなわち イが正しい。
?選択肢ごとの解説
ア ×入次数 2 のノード5 であり、最大ではなく 2 番目に大きいノードを選んだ誤りである。
イ ○辺の終点 v を数えると、ノード3へは 1→3, 2→3, 4→3 の 3 本、ノード5へは 2→5, 4→5 の 2 本、他は 0 本である。indeg={0,0,3,0,2} の最大はノード3（3本）なので best=3、すなわち イが正しい。
ウ ×ノード2 は入次数 0 であり、辺の始点（出る側）を誤って数えた、入次数と出次数を取り違えた誤りである。
エ ×ノード4 も入次数 0 であり、入ってくる辺が 1 本もないノードを選んだ誤りである。
✎くわしく
入次数は『辺の終点 v』を数えることで求まる。比較ループは『より大きい場合のみ更新』とすることで、同数のときは先に見た（番号の小さい）ノードが保持され、タイブレーク規則が自然に満たされる。
✓本番での押さえどころ
試験のコツ
入次数は矢印の『先』、出次数は矢印の『元』。各辺を1本ずつ終点に加算し、表を作って最大を読む。
覚え方
『入次数は刺さってくる矢の本数』と覚える。
よくある誤り
始点 u を数えて出次数を求めてしまう、等号付き比較で同数時に後のノードへ更新してしまうミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-0154