DAGとトップソート

Question

"プレ番号の増加に応じてDAGの頂点を配置するとトポロジカルソートになります。"明らかに真実ではありませんが、なぜそうではないのか分かりません。グラフが指示され、サイクルを持たない場合、我々が頂点を訪れる順序は、必ずしもトポロジー的に正しい順序であるべきではないか？

Answer 1

プレ番号を増やして配置しても、有効な位相分類が保証されるわけではありません。このグラフを考えてみましょう：

A 
    ↓ 
B → C → D 

このグラフの2つの有効なトポロジカル順序は以下のとおりです。

A, B, C, D 
B, A, C, D 

あなたはCで始まるノードを訪問した場合、一つの可能​​な事前に番号順は次のようになります。

C, D, A, B 

これは有効なトポロジカルな順序ではありません。さらに簡単な例は、このグラフである：

B → A 

ありつの有効なトポロジカル順序が明確であるが、私たちは最初のプレ数でソートを訪問した場合、結果の順序が逆方向になります。