排序當只有特定對象可比較時才設置

我有一組唯一的數據。比方說，它看起來像這樣：排序當只有特定對象可比較時才設置

0: domainA.org -> domainB.org 
1: domainY.org -> domainZ.org 
2: domainB.org -> domainC.org 
3: domainD.org -> domainE.org 
4: domainX.org -> domainY.org 
5: domainC.org -> domainD.org

爲了與domainA.org爲BCD和doimanY.org數據E和複製到X和Z，我需要遍歷這組按以下順序：

0: domainA.org -> domainB.org 
2: domainB.org -> domainC.org 
5: domainC.org -> domainD.org 
3: domainD.org -> domainE.org 

4: domainX.org -> domainY.org 
1: domainY.org -> domainZ.org

如果在A -> B -> C -> D -> E之前處理X -> Y -> Z它們並不相關，那並不重要。

對每個「類別」進行排序例如數據的每一個獨立部分都是非常簡單的。我使我的包裝對象sourceDomain -> destinationDomain實現了Comparable，並使用SortedSet爲我進行排序。現在是這個問題。
這是我comparteTo實現看起來是這樣的：

if (source.equals(other.destination)) { 
    return 1; 
} else if (destination.equals(other.source)) { 
    return -1; 
} 
return 0;

它只是能夠比較兩個對象，如果他們在最後名單otherwhise它「對待」的其他物體一樣彼此相鄰。
（更何況，如果compareTo在某個點返回0，那麼TreeSet不會添加項目）因此，它不會正確排序示例1中顯示的數據。
我的想法是迭代源集並添加比較每個其他條目的條目，並創建分離集，我可以在完成排序後將它們連接在一起。
這樣的複雜度至少是n^2，這很糟糕。
我的問題：我們可以做得比那更好嗎？

來源

2017-06-06 RoiEX

什麼時候源不等於other.destination和目標不等於other.source？在這種情況下，該方法返回0 –

正確，這是問題...沒有辦法確定這兩個對象如何相互關聯 – RoiEX

你正在尋找的東西是圖中的拓撲排序。有各種算法可以解決這個問題，在the Wikipedia article的僞代碼中可用。

最容易實現的是深度優先搜索，下面有些複製：

L ← Empty list that will contain the sorted nodes 
foreach node n do 
    if not marked n then visit(n) 

function visit(node n) 
    if n has a temporary mark then stop (cyclic dependency found!) 
    if n is not marked (i.e. has not been visited yet) then 
     mark n temporarily 
    for each node m with an edge from n to m do 
     visit(m) 
     mark n permanently 
     unmark n temporarily 
     add n to head of L

這在大多數的時間複雜度爲O（節點+邊緣），並在你的情況看來，節點=邊緣，這樣就足夠快了。

來源

2017-06-06 10:14:37

排序當只有特定對象可比較時才設置

回答

相關問題