例えば、A -> B, B -> C, A -> C という枝があった場合に、短い A -> C を切る (取り除く)。
- 到達できるパスの中で一番長いものを残す
- 到達可能性を保存したまま、枝の最も少ないグラフを求める
treeの性質
無向エッジの場合、二つのノード間のパスは一通りしかない。
DAG (Directed Asyclic Graph)
一つの枝からことなるノードに達するパスが複数あり得る。
勘
nから1ステップで達するノードmに対して、nからmに到達する2ステップ以上の枝があるならば、 (n,m)を取り除く。
nから2以上でmに達するパスは取り除けない。なぜならばnから1ステップで到達できるノードに到達 できなくなるから。
To Home