排序和拓撲排序有什麼區別？

它們是相同的還是不同的東西？

2012-02-02 Samselvaprabu

https://en.wikipedia.org/wiki/Sorting_algorithm | https：//en.wikipedia.org/wiki/Topological_sorting – 2012-02-02 10:24:06

在抽象層面上它們是連接的：正如Saeed和Stefan所說，它是總訂單和部分訂單之間的差異。這是一個非常簡潔的描述，但有時候在學習時沒有幫助。

總的訂單意味着，在沒有重複的情況下，當您排序某些內容時，您將得到一個唯一的正確答案。如果按升序排序3,6,2，最好得到一個答案：2，3，6.

部分訂單有點鬆散。典型的例子是你穿上衣服的順序：你可以穿上你的短褲，然後是褲子，然後是你的襪子，然後是你的鞋子。這是一個有效的訂單。或者你可以做短褲，襪子，褲子，鞋子。但直覺上，你不能做短褲，褲子，鞋子，襪子。把襪子放在鞋子後面是沒有意義的。

爲了形式化該敷料示例，您通常會將帶有動作（「穿上鞋子」）的依賴關係圖顯示爲節點，並指示顯示哪些節點必須位於其他節點之前的依賴關係圖。拓撲排序是圖形中所有節點的排序，就像尊重弧段一樣。意思是，如果從襪子到鞋子都有弧線，那麼襪子最好在鞋子前排序。

再次，在抽象層次上，它們是連接的。但他們絕對不是同一件事。

來源

2012-02-02 14:52:48 Novak

如果你是布蘭妮，你可以把你的字符串後短...（我已經出局） – Kheldar 2012-02-02 14:54:23

@Novak：非常簡單和易於理解的例子。我想我永遠不會忘記這種拓撲排序。你是大學教授嗎？如果是這樣，你的學生真的很幸運。 – Samselvaprabu 2012-02-03 05:48:28

你很善良，但不，我只是一名博士生。我發現我必須在自己的頭腦中直接得到低級直覺，以幫助我記住，有時幫助我理解數學描述。數學是抽象力量的地方，但對於我來說，圖片和故事就是直覺所在。 – Novak 2012-02-03 19:06:45

拓撲排序通常是指查找符合某個部分順序的總順序，例如有向無環圖中的可達性關係。

來源

2012-02-02 10:18:38

如果總訂單可用，則可以將每個對象與每個對象進行比較。在這種情況下，你可以對wrt進行排序。該訂單。示例是wrt的整數。 >（或<或< =，...）或字符串wrt。字典順序。如果你有一個總的訂單排序是可能的。

如果只有部分訂單可用，則不是每個對象都可以與其他每個對象進行比較。只有某些對象之間存在關係。一個例子是編譯單元之間的依賴關係。拓撲排序是查找對象排序的任務，使得部分順序得到遵守（例如，通過編譯依賴於這些單元之後的某個其他單元的單元）。這裏有幾種解決方案（即排序）是可能的：如果A取決於B並且存在一些其他單元C，則可能的編譯序列是B，A，C和C，A，B（其中A在B之前編譯的每個序列）。

來源

2012-02-02 10:20:26 Stefan

在拓撲排序中，我們在partially ordered set上工作，但在正常排序中，我們在total ordered set上工作。

在拓撲排序中，集合中的一對元素之間可能沒有任何關係，就像在有向圖中一樣，在某些節點之間沒有任何關係。在正常排序中，集合中的所有元素都有關係。例如，在一組數字中，我們有關係<，>，=所有對之間，所以它是總的有序。

來源

2012-02-02 10:26:12

排序和拓撲排序有什麼區別？

回答

相關問題