データ構造とアルゴリズム
作業 A〜E に「A は C より前」「B は C より前」「C は D より前」「B は E より前」「E は D より前」という順序の制約がある。すべての制約を満たす作業の順(トポロジカルソートの結果)はどれか。
- AA, C, B, E, D
- BB, A, E, C, D
- CB, E, D, A, C
答えと解説を見る
正解：B. B, A, E, C, D
B, A, E, C, D では、A と B が C より前、C と E が D より前、B が E より前で、5つの制約をすべて満たします。A, C, B, E, D は B より前に C を行っているので「B は C より前」に反し、B, E, D, A, C は C より前に D を行っているので「C は D より前」に反します。トポロジカルソートは、向きがあって閉路のないグラフ(DAG)で、すべての辺が前から後ろへ向くように頂点を並べる操作で、入ってくる辺のない頂点から順に取り出す方法(カーンの方法)や深さ優先探索で求められます。答えは1つとは限らず、この例では制約を満たす順が5通りあります。
- A. C を B より前に行っており、「B は C より前」に反します。
- B. 正しい。5つの制約をすべて満たしています。
- C. D を C より前に行っており、「C は D より前」に反します。