切断されたDAGのトポロジカルソート順序

Question

数字0,1,2が有向非循環グラフのノードで、1つのエッジがある場合：1 -> 2です。有効な注文は次のとおりです。

1,2,0 
0,1,2 
1,0,2 

正しいですか？私は最後の注文についてのみ確信しています：1,0,2それは有効ですか？

Answer 1

はい、あなたは正しいです。

definitionによると、トポロジカル秩序のための唯一の条件は、すべての有向エッジu->vのためのuをvの前に来なければならないということである。それはV直前に来るべきであると言われていません。

タスクを表現するために頂点を考えてみましょうあなたは準備ができていると言います。 0はネクタイ、1は靴下、2は靴を履いています。従って、1は2（1→2）の前に来る。ご覧のように、あなたが書いた最後の注文はトポロジカルな注文であるとみなすことができます（靴下を履いてから靴を履いてください）