アルゴリズムとプログラミング
トポロジカルソートが適用できるグラフの条件として正しいものはどれか。
ア.連結していない孤立ノードが存在する場合は適用できない。
イ.無向グラフであれば、辺の方向に関係なく適用できる。
ウ.有向非巡回グラフ（DAG：Directed Acyclic Graph）にのみ適用できる。正解
エ.グラフに閉路（サイクル）が存在するほど効率よくソートできる。
解説
トポロジカルソートは「工事の段取り組み」。「基礎→柱→屋根」という依存順序があるDAGにしか適用できません。グルグル回る依存（循環依存）があると永遠に順番が決まりません。
なぜ ウ が正解か
トポロジカルソートは有向グラフの全ノードを「辺の向きに逆らわない順番」に並べる操作です。これが可能なのはDAG（有向非巡回グラフ）のみです。 ・「有向」→辺に方向がある（依存関係がある） ・「非巡回」→閉路がない（循環依存がない） DAGでは必ずトポロジカル順序が存在し、DFS（深さ優先探索）やKahnのアルゴリズムで求められます。ビルドシステムやタスクスケジューリングに応用されます。
出典: AI生成問題（学習用）