アルゴリズムとプログラミング
基本情報技術者試験｜有向グラフを次の辺リストで与える（u → v は u から v への辺）。 1→3, 2→3, 4→3,…
有向グラフを次の辺リストで与える（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 本もないノードを選んだ誤りである。
アルゴリズムとプログラミングの他の問題
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,…有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3, 2→4, 5→1
次の手続…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0154