FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次のトポロジカルソートを実行したとき、戻り値はどれか。 整数…
問題
次のトポロジカルソートを実行したとき、戻り値はどれか。
整数型の配列の配列: edge ← {{3}, {3,4}, {5}, {5}, {6}, {}}
整数型の配列: indeg ← {0, 0, 2, 1, 2, 1}
整数型の配列: q, order
enqueue(q, 1)
enqueue(q, 2)
while (qが空でない)
v ← dequeue(q)
append(order, v)
for (edge[v]の各要素 u を先頭から順に取り出す)
indeg[u] ← indeg[u] - 1
if (indeg[u] = 0)
enqueue(q, u)
endif
endfor
endwhile
return order[4]- ア 3
- イ 4（正解）
- ウ 5
- エ 6
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
入次数が0の頂点1,2からキューに入ります。1を処理しても3の入次数はまだ1残ります。2を処理すると3と4の入次数が0になり、この順にキューへ入ります。
| 取り出し | 新たに追加 | order |
|---|---|---|
| 1 | なし | {1} |
| 2 | 3,4 | {1,2} |
| 3 | なし | {1,2,3} |
| 4 | 5 | {1,2,3,4} |
したがってorder[4]は4です。辺を消した後の入次数更新を順に追う必要があります。
選択肢の見分け方：3は3番目、5は4の処理後に入る頂点、6はさらに後の頂点です。入次数が0になった瞬間にキューへ入る順番を追いましょう。
このアルゴリズムの正体：これは入次数0の頂点を順にキューへ入れていくKahn法（幅優先によるトポロジカルソート）です。各頂点を1回ずつ取り出し、その出辺をたどって隣の入次数を1減らすため、計算量は頂点数Vと辺数Eに比例するO(V+E)です。複数の頂点が同時に入次数0になったときの並び順は、キューへ入れた順序（ここでは2の処理で先に3、次に4）で決まる点に注意しましょう。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。