C ++和Swift中的不交集联合

您是否曾经想过，当您开车开车时，导航系统如何根据基于输入数据的变化（例如交通拥堵和错位）校正从当前位置到目的地的最佳路线？

这是最小生成树（MST）问题的实时实际应用之一，其中像Kruskal算法那样的算法试图解决该问题。在本文中，我们将学习Kruskal算法中使用的主要数据结构，以便有效地解决MST问题。

在本文中，我们将快速完成：

想象一下有一个图，就像下面的图片一样。您被要求非常快速地进行两个查询：
1. unionSets，即将两个集合合并在一起。
2. isSameSet，即查找两个节点是否在同一集合中。

Disjoint-set数据结构使我们可以非常快速地确定两个项目是否在同一集合中（或等效地确定两个顶点是否在同一连接的组件中），并且还可以非常快速地将两个集合联合（或等效地组合两个连接的组件）成为一个连接的组件）。

联合查找算法是一种对此类数据结构执行两个有用操作的算法：
查找：确定特定元素位于哪个子集中。这可用于确定两个元素是否在同一子集中。
联合：将两个子集合并为一个子集。

联合查找算法可用于检查无向图是否包含循环。此方法假定该图不包含任何自循环。我们可以跟踪一维数组中的子集。

在下图中，让我们找出在此图是否有周期的情况下购买此联合查找算法。

对于此图中的每个边缘，请使用边缘的两个顶点制作子集。如果两个顶点都在同一子集中，则会找到一个循环。

然后创建一个父数组并将其memset为-1（即，将-1作为所有数组的初始值）。然后一一处理所有这些边缘。

  0 1 2->节点。 
  -1 -1 -1->父数组。

边缘0–1：查找顶点0和1所在的子集。由于它们位于不同的子集中，因此我们将它们合并。要采用并集，请将节点0设为节点1的父级，反之亦然。

  0 1 2->节点。 
  1 -1 -1->节点编号1是节点0的父节点。

我们将动态创建父数组和sz数组，我们还将需要一个私有方法来获取当前节点的父节点，最后，在私有成员部分中，我们将需要一个swap方法。

在公共成员部分，我们需要一个构造器 ，该构造器将使用图的大小，并用unionSets方法将两个集合合并在一起，使用isSameSet方法来找出两个节点是否位于同一集合中，最后当然，我们需要一个析构函数。

在实现这些方法时，从find_parent（）开始 。
这里的想法是将节点的父级保存在父级数组中，因此，当您需要此信息时，它将以摊销的O（1）复杂度而不是O（n）的形式提供给您信息。

在same_set（）中 方法，我们将只比较两个节点的父节点。如果它们匹配，则它们在同一组中。最后，在union_sets（）方法中，您将找到两个节点的父节点，然后对其进行合并。如果它们不在同一个集合中。

构造函数将使用从0到n的节点数填充父数组。

创建一个新的Swift Playground，然后创建一个名为DSU的类。在这一步中，我将把C ++代码转换为Swift。我很快想出了一个非常相似的东西。

注意，我需要在适当的位置更改属性，因此我将inout关键字用作函数的参数。

传递给Swift函数的所有参数都是常量，因此您无法更改它们。如果需要，可以传入一个或多个参数inout ，这意味着可以在函数内部更改它们，这些更改反映在函数外部的原始值中。

本文中的所有代码都在我的GitHub上。

HassanElDesouky / DisjointSetUnion
C ++和Swift中的不相交集联合的实现– HassanElDesouky / DisjointSetUnion github.com

Boost Graph Library使用此数据结构来实现其增量连接组件功能。它也是实施Kruskal算法以查找图的最小生成树的关键组件。

我玩过它并解决了C ++中的MST问题很开心，仅通过实现此数据结构，我学到了很多东西。因此，我想尝试在Swift中实现它。

感谢您的阅读，希望您阅读本文愉快。如果您有任何想法，请通过Twitter与我联系。

您可以从以下网站了解有关DSU的更多信息：