算法將相關項目

我有一組項目。該集合中的每個項目可以與一個或多個其他項目相關。我想建立一個算法，將直接或通過其他項目關聯在一起的項目分組。算法將相關項目

實施例： 我的集合爲{A，B，C，d，E，F}

a和b是相關的。 c與d有關，d與e有關。

該算法應該產生下列基團： {A，B}，{C，d，E}，{F}

這樣做的高效算法的任何想法？在此先感謝:-)

來源

2012-03-29 Super Chafouin

不'了'與'B'，暗示有關''了'B'？ – st0le 2012-03-29 04:18:38

是的，它的確如此。也許我用的「關係」這個詞是不夠的？ – 2012-03-29 04:23:54

太好了。我的答案成立。 – st0le 2012-03-29 04:24:27

使用Union Find。速度非常快。使用路徑壓縮，複雜度降低爲O（A（N）），其中A（n）是阿克曼函數的逆。

來源

2012-03-29 04:20:54 st0le

令人驚歎。不想看到這個下限的證明。 – 2012-03-29 04:53:16

它確實是！ :) – st0le 2012-03-29 05:28:14

好吧，我讀了Tarjan，馬上想到了Lengauer-Tarjan算法，並且那些過去的編譯器課程的所有內存都閃回了:) – 2012-03-29 08:14:32

要擴大st0le的回答有點...

所以，你必須元素的列表：

A，B，C，d，E，F

和聯繫列表：

AB
CD
德

初始化通過將EAC h元素在它自己的組中。

然後，遍歷您關係的列表。

對於每個關係，發現每個元素是一個成員，然後團結的那些基團的基團。

所以在這個例子：

1: init -> {a}, {b}, {c}, {d}, {e}, {f} 
2: a-b -> {a,b}, {c}, {d}, {e}, {f} 
3: c-d -> {a,b}, {c,d}, {e}, {f} 
4: d-e -> {a,b}, {c,d,e}, {f}

你會明顯要檢查所有的關係。取決於你如何實現'find'部分會影響算法的效率。所以你真的想知道在一組元素中找到元素的最快捷方式是什麼。一種天真的方法將在O（n）中做到這一點。您可以通過保持一個記錄哪個組給定的元素是在這個提高。然後，當然，當你團結兩組，你將不得不更新您的記錄。但這仍然有幫助，因爲您可以將較小的組合併成較大的組，從而節省您需要更新的記錄數量。

來源

2012-03-29 04:46:22 soundslikeneon

算法將相關項目

回答

相關問題