ソートとトポロジカルソートの違いは何ですか？

Question

ソートとトポロジカルソートの違いは何ですか？

それらは同じか異なっていますか？

Answer 1

抽象的なレベルでは、それらは接続されています.SaeedとStefanは言うように、それは総注文と部分注文の違いです。これは非常に簡潔な説明ですが、学習するときに役立たないこともあります。

合計順序とは、繰り返しがない場合、何かを並べ替えるときに、固有の正解を1つだけ得ることを意味します。 3,6,2を昇順にソートすると、1つの答え、2、3、6を得たほうがよいでしょう。

部分的な順序が少し緩いです。標準的な例は、あなたが服を着る順序です：あなたはあなたのパンツ、次にあなたのズボン、次にあなたの靴下、そしてあなたの靴を置くことができます。それは有効な注文です。または、ショーツ、ソックス、ズボン、靴をすることができます。しかし、直感的に、あなたはショーツ、ズボン、靴、ソックスをすることはできません。靴の後に靴下を着用するのは意味がありません。

ドレッシングの例を正式化するには、通常、行動（「靴を履く」）をノードとして表示し、どのノードが他のノードに先行する必要があるかを示す円弧を表示します。トポロジカルソートは、アークを尊重するようなグラフ内のすべてのノードの順序付けです。意味は、靴下から靴までの弧がある場合、靴下は靴の前に順番に来る方がよい。

再び、抽象的なレベルで、それらは接続されています。しかし、彼らは絶対に同じことではありません。

Answer 2

トポロジカルソートは、通常、ある部分的順序に従うトータルオーダー、例えば、有向非循環グラフにおける到達可能性の関係を見つけることを指します。

Answer 3

すべてのオブジェクトを利用できる場合は、すべてのオブジェクトをすべてのオブジェクトと比較できます。この場合、wrtをソートすることができます。その順序。例は整数wrtです。 >（または<、または< =、...）または文字列wrt。辞書編集による順序付け。トータルオーダーがあればソートが可能です。

部分的な順序しか利用できない場合、すべてのオブジェクトを他のすべてのオブジェクトと比較できるわけではありません。特定のオブジェクト間の関係のみが使用可能です。一例は、コンパイル単位間の依存関係です。トポロジカルソートは、部分的な順序が尊重されるように（例えば、これらのユニットの後のある他のユニットに依存するユニットをコンパイルすることによって）オブジェクトの順序を見つけるタスクである。 AがBに依存し、他のユニットCがある場合、可能なコンパイルシーケンスはB、A、C、C、A、B（AがBより前にコンパイルされるすべてのシーケンス）である。

Answer 4

トポロジカルソートでは、partially ordered setで作業しますが、通常のソートではtotal ordered setで作業します。

トポロジカルなソートでは、有向グラフのように、セットの要素のペアの間に関係がないかもしれませんが、いくつかのノードの間には関係はありません。通常のソートでは、セットの要素のすべてのペアに関係があります。例えば、数の集合では、すべての対の間に関係<、> =があるので、それは合計順序です。