python-3.x - 在python3中联合查找

Question

我知道一般如何实现联合查找，但我在考虑是否有办法利用 python 中的集合结构来实现相同的结果。例如，我们可以很容易地联合集合。但我不确定如何仅使用集合来确定两个元素是否在同一个集合中。所以，我想知道除了通常的实现之外，python 中是否有支持这种操作的数据结构？

score 1 · Accepted Answer

您总是可以通过将其可视化为一棵树及其通过根相互连接的节点来解决此问题，然后如果您想知道两个节点是否连接，则查找该树。如果您要比较的两个节点具有相同的根（它们在同一棵树中），则它们是连接的。

要连接两个节点，只需转到它们所在的每棵树的根，并使一个根成为另一个根的父级。

树节点之间的连接可以通过支持它的语言中的指针来建立，但如果您的语言不（python），那么您可以通过通过数组存储位置和链接来创建自己的指针。

该数组将使其位置代表您的节点，其中的值代表特定节点与其根的连接。一开始，数组中的位置是用节点号填充的，因为节点最初没有父节点，但是当你连接节点时，根会改变，数组必须表示这一点。实际上，存储在那里的值是根的标识符。

但是首先尝试直观地可视化问题，而不是考虑数组和过多的数学人工制品。直观地处理它会使解决方案听起来很平庸，并且可以在编写代码时提供很好的指导。

我这样说是因为我观看了我刚刚发布的 Robert Sedgewick 的视频，其中包含解决方案的图形模拟，并且我自己实现了，而没有过多关注他书中的代码。视频给我的直觉比任何数学都更有价值。

它将帮助您将节点封装到一个类中，使用以下方法：

顾名思义，第一种方法将您从一个节点带到树上，直到找到它的根，然后将其返回。

如果你用这个方法比较两个节点（实际上是它返回的根），你很容易通过比较它们的根来知道它们是否连接。

一旦你想把它们连接起来，你就爬上两个节点的树，并要求一个根将另一个作为它的父节点。

树木可以长得非常高（抱歉，我没有使用官方命名法，但这对我来说是有意义的），所以当你以后必须爬树时，这种简单的方法会变得非常慢。

为了防止树变得高，不要只是将一个根设置为没有标准的另一个根，而是将最小的树（根据高度，而不是元素的数量）附加到最高的树。

为此，您需要知道每棵树的高度，并且您可以将这些信息存储在它们各自的根上（在您的情况下通过额外的数组，或者在其他语言中通过每个节点的额外指针）。每当另一棵树连接到它时，都应该更新此信息。

一棵树不可能知道她刚刚附上了一棵新树，因此每棵附在第二棵树上的树都会通知第二棵树更新其高度，这一点很重要。

该信息可以发送到第二棵树的根，然后用于判断（如前所述）哪棵树最小。请记住，将一棵小树连接到一棵大树上，而不是相反，这将为您节省大量时间。

score -1 · Accepted Answer

-1

你想要这样的东西吗？

myset = ...
all(elt in myset for elt in (a,b))

于 2016-02-23T03:12:06.630 回答

2 回答 2