不相交集合数据结构

Question

作为一个逻辑问题，在什么情况下（以及在什么情况下）应该不相交的集合对我有用？例如，优先级队列在我需要在运行时添加更高优先级的元素以便在队列中已经存在的较低优先级元素之前服务于我的情况下帮助我......但是我似乎没有找到“实际”用法为不相交的集合。谢谢一堆！

Answer 1

这是一个非常宽泛的问题。对于不相交集有很多应用。

假设我正在为我最喜欢的操作系统编写一个软件包维护工具，其基础是从源代码构建软件（可以在免费的BSD上完成）。它需要跟踪包之间的依赖关系。在构建和安装大包时，它会递归地获取，构建和安装任何所需的依赖关系。

如果我能够一次启动几个独立构建将会很好。也就是说，如果我发布的版本套件是不相交，那将会很不错。如果他们不是，我将不得不依次串联工作通过交叉点，直到我得到不相交的集合。