不相交集合數據結構

Question

作爲一個邏輯問題，在什麼情況下（以及在什麼情況下）應該不相交的集合對我有用？例如，優先級隊列在我需要在運行時添加更高優先級的元素以便在隊列中已經存在的較低優先級元素之前服務於我的情況下幫助我......但是我似乎沒有找到「實際」用法爲不相交的集合。謝謝一堆！

Answer 1

這是一個非常寬泛的問題。對於不相交集有很多應用。

假設我正在爲我最喜歡的操作系統編寫一個軟件包維護工具，其基礎是從源代碼構建軟件（可以在免費的BSD上完成）。它需要跟蹤包之間的依賴關係。在構建和安裝大包時，它會遞歸地獲取，構建和安裝任何所需的依賴關係。

如果我能夠一次啓動幾個獨立構建將會很好。也就是說，如果我發佈的版本套件是不相交，那將會很不錯。如果他們不是，我將不得不依次串聯工作通過交叉點，直到我得到不相交的集合。