使网络连接所需的最小操作数

在此问题中，我们得到了一个包含 n 个组件的网络。这些组件相互连接，连接信息以二维数组的形式给出。在此问题中，我们的任务是找到连接所有组件所需的最小附加连接数。如果无法连接所有组件，则返回 -1。

示例

输入: N = 5, c = [[0, 1], [1, 2], [0, 2], [1, 3], [0, 3]]

输出 1

输入: N = 6, c = [[0, 1], [1, 2], [0, 2], [1, 3], [0, 3]]

输出 2

方法 - 1

在此问题中，我们将使用并查集来查找给定网络中附加连接的数量。并查集是一种数据结构。这种数据结构存储不包含任何共同元素的集合。因此，得名并查集。附加连接的数量将告诉我们可以进行多少新连接来连接整个网络。如果附加连接的数量少于 组件数 - 1，则网络可以连接，并且该网络将包含 n-1 条边，其中 n 是图中节点的总数。如果不满足条件，则返回 -1。

我们将遵循以下步骤

• 我们将从给定的二维连接数组构建邻接表。
• 然后，我们将使用 Disjoint 类创建一个并查集，并传入组件数量。
• 下一步是检查图中的组件数量。我们将使用 DFS 遍历来找到组件数量。调用 DFS 函数的次数将等于图中组件的数量。
• 最后一步是检查条件：如果组件数 - 1 小于或等于附加边的数量。如果是，则我们可以连接图的所有组件。
• 最后一步是返回连接整个网络所需的最小边数。

上述方法的实现如下。

代码

输出

1

时间复杂度: DFS 需要线性时间来遍历图中的所有节点。并查集上的操作需要常数时间。由于节点总数为 n，因此此方法的时​​间复杂度为 O(n)。

空间复杂度: 我们使用了额外的空间来存储集合；因此，此方法的空间复杂度为 O (e + n)，其中 e 是边的数量，n 是节点的数量。

方法 - 2

在此方法中，我们将使用最小生成树方法来查找连接整个网络所需的最小连接数。

最小生成树

假设我们有一个无向图。图的边是带权重的。图有 N 个顶点和 E 条边，设 S 为包含边的集合。最小生成树是集合 S 的子集，它包含足以跨越完整树或图的边，并且其总权重是所有可能的边集合中最小的。因此，最小生成树包含 N-1 条边，其总权重最小。

我们可以在本问题中使用此概念，因为我们还需要 N-1 个连接来连接整个网络。

让我们看看该方法的算法：

• 我们将通过初始化一个映射（map）来开始。在 Python 中，我们需要创建一个字典对象来利用映射的特性。此字典将存储给定网络连接的邻接表。
• 我们还将创建一个与邻接表大小相同的二维数组。我们将初始化该数组，并将所有索引的值设置为 0。此数组将跟踪图中已访问的节点，这在遍历过程中是必需的。
• 现在，利用我们获得的连接信息，我们将创建图的邻接表。使用邻接表，我们可以计算图中的边数。
• 现在，我们已经以邻接表的形式创建了图的结构，我们可以使用 DFS 算法来遍历完整的图并计算图中连接组件的总数。
• 现在，我们需要计算图中存在的附加边数。要计算附加边数，我们将使用此公式
  • 附加边数 = 总边数 - [(总节点数 - 1) - (总组件数 - 1)]
  • 这将给出我们可以从图中删除的边的计数。
• 现在，由于我们可以进行的连接数受到已有连接数的上限限制，因此我们需要检查是否存在连接网络的方法。
• 我们可以使用以下条件来检查这一点
  • 附加边数 > 总组件数 - 1
  • 如果满足此条件，则我们可以使用这些附加边连接网络中不连通的组件。连接网络所需的最小边数或连接数将等于总组件数 - 1。
  • 如果不满足此条件，则我们无法使用给定数量的连接来连接网络，因此我们将返回 -1。

下面是该方法在 Python 中的实现。

代码

输出

1

时间复杂度: 在此方法中，我们使用了 DFS 来查找所需的最小连接数；因此，此方法的时​​间复杂度为 O(n)，其中 n 是图中的节点数。

空间复杂度: 我们使用了额外的空间来存储数组并跟踪已访问的节点。因此，此方法的空间复杂度为 O(n)。